二分搜索套路入门
二分搜索套路框架
二分查找是在一个有序数组中找到目标元素的一种查找方法,它的大致思想是:将区间分为两半,对比目标元素是在左半边还是右半边,然后递归地在左(右)半边区间进行查找。
二分搜索分为三类:
- 寻找某个数
- 寻找某个数的左边界
- 寻找某个数的右边界
虽然这三类看似差不多,主要框架也差不多,但是在细节上是有所区别的,所以本节内容是主要讲解细节上面的差异,搞懂这些细节上的差异,是我们这一节的目的。既然只有细节上有差距,那么先来看一下总的框架:
1 | int binarySearch(int[] nums, int target){ |
细节介绍
其实这些细节都是有联系的我们一个一个来看:
细节1:二分查找的区间表示形式
1.left, right = 0, nums.length-1
, 这种方法指的是指left
指向第一个元素,right
指向最后一个元素,是一个左闭右闭区间,用数学的语言来表示就是“[a, b]”。
2.left, right = 0,nums.length
, 这种方法指的是left
指向第一个元素,right
指向最后一个元素,是一个左闭右开区间,用数学的语言来表示就是“[a, b)”。
其实细节1讲述了描述左右边界的定义,两个指针分别代表什么含义,在下面的内容中,都将用这些定义来描述区间范围。
细节2:while()循环里的条件使用“<”还是“<=”
该问题就需要考虑细节1中用的是那种表示形式来表达区间了,因为while()循环里的条件是需要继续查找的条件,那什么是中止条件呢?答:区间为空的时候。下面用细节1中的两个表示形式来举例:
[a, b] 左闭右闭区间:循环在a <= b 时都可以继续查找,因为在a <= b 时,[a, b] 中是有元素的,所以应当使用“<=”。中止条件是left == right+1。
[a, b) 左闭右开区间:循环在a < b 时都可以继续查找,因为在a < b 时,[a, b) 中是有元素的,所以应当使用“<”。中止条件是left == right。
注: 当然区间表示方法不止这两种,你也可以自己定义。但是循环里的条件就取决于区间表示形式,所以细节2是依赖于细节1的。至于为什么是中止条件是这两个,模拟一下就行啦。
细节3:各个条件中指针该怎么转移
转移的方式其实只有两种:
1.左指针向右移,这代表着目标元素在右半边,那怎样才能将左指针移动到能够完整的包含右半边所有元素呢?这就需要参考细节1中的表示形式,[a, b]的话就需要left = mid + 1
,因为小于等于mid
的都已经考虑过了,[mid+1, right]包括了所有右半边的元素。[a, b)的话就需要left = mid+1
,因为mid
访问过了,而left指的是左指针,是闭区间,两种形式都是闭区间,所以转移方式相同
2.右指针向左移,这代表着目标元素在做半边。[a, b]的话就需要right = mid - 1
,因为mid
访问过了。而[a, b)中是不一样的,它的右指针指的是最右元素的下一个位置,最后一个元素是mid-1
,所以right = mid
。
当然,这两种方式具体放在哪里还需要考虑是哪一类的二分搜索。
细节4等到3种二分搜索介绍完再说
三类二分搜索具体介绍
为了减少篇幅,这里只介绍区间表示为左右都闭的方式
1.寻找某个数
1 | int binarySearch(int[] nums, int target){ |
这里都是闭区间,所以采用left = mid + 1
和right = mid - 1
来转移指针。但是如果nums[]
中好几个元素等于target,那就产生了“target的左侧边界”和“target的右侧边界”的需求。
2.寻找左侧边界的二分搜索
1 | int left_bound(int[] nums, int target){ |
由于都是闭区间,所以采用的转移指针方式和循环条件都是确定的。[2]和[3]都很好理解,属于我们的常规操作,那么[1]又是怎么理解的呢?看这个之前我们需要了解在找不到的情况下,左右指针分别在什么位置。中止条件是left == right + 1
,找不到的数大于right
,小于left
。
现在再来理解[1],为了寻找左侧边界即使找到了target
,也要继续往左边找,这不就是要找小于target
的第一个数嘛。虽说是要找小于target
的第一个数,但是这个数并不存在,所以,中止条件只能像是这样,就像这样,left
刚好落在了最左边的target
上。就是我们找到的最终目标,只要返回left
就行了。
但是新问题又来了,如果本身就没有target
怎么办?那只要判断一下是不是nums[left]
是不是target
就行了,但是这里又有个细节,left
是可能超出num[]
范围外的,left
的取值范围是[0, nums.length],nums[nums.length]可能右溢出,所以需要先判断是否右溢出。如果不存在的话,就返回-1
。
3.寻找右侧边界的二分搜索
1 | int left_bound(int[] nums, int target){ |
基本与找左侧边界类似,便不再赘述了。