前言
在做算法题时，有的时候会用到二分搜索，我自己总结一下其规律，来和大家分享，开整。
题目
我先引入一个题，这个题很简单，即搜索一个数，存在则返回索引，不存在则-1。
import java.util.*;
/**
* @author 弈鸣coding
* @data: 2022/2/26
*/
class Test1 {
public static int twoS(int[] nums, int target){
int left=0;
//注意右区间是nums长度减一
int right=nums.length-1;
while (left<=right){
int mid =left+(right-left)/2;
if (nums[mid]==target)
return mid;
else if (nums[mid]<target)
left=mid+1;
else if (nums[mid] > target)
right = mid-1;
}
return -1;
}
}
1.分析
我们初始化的right是nums.length-1，是数组最后一个元素的索引，索引while循环中的条件是<=而不是<。
索引这两种方式是有不同的功能的：
- nums.length-1
这种表达形式相当于选择的区间都是闭区间，类似于
[left, right]
- nums.length
这种表达形式相当于选择的区间左闭右开区间，类似于
[left, right)
为什么右开呢？
因为索引的大小为nums.length的值是越界的
如上图，数组的长度为5，已经超过了索引值
2.while终止条件
while什么时候终止呢，下面分为两种讲解
- while (left<=right)
在这种情况下，while的循环终止条件就是left=right+1，也就是说左区间大于右区间时while会终止循环，表现形式为 [right+1,left] (这里所指的区间不是数组里面的值，而是索引的值)!！
举例：
我们要查找8这个数，right=nums.length-1，所以right=4，
第一步： mid=2，nums[2]=7,很明显目标值8大于7，left就会加1
第二步： right=4，left=1，mid=2，nums[2]=7，目标值8大于7，left就会继续加1
第三步： right=4，left=2，mid=3，nums[3]=1，远远大于1，left继续加1
第四步： rigth=4，left=3，mid=3，nums[3]=1，还是大于1，left继续加1
第五步： right=4，left=4，mid=4，nums[4]=6，target=8大于6，left继续加1
来到最后一步： right=4，left=5
left=5大于right=4，跳出循环， 这就是前面说的while的循环终止条件就是left=right+1
写这么多也是希望大家都能看得懂
- while (left<right)
再来看这种情况，终止的条件为left=right，也就是区间为 [left,right] 的形式
再举列子：
[3,3]的区间，这个区间的可取值为3，但是循环的结束条件为left<right，索引3对应的值就会被漏取，当然这种情况是可以避免的，我们只要在循环结束时，在判断一次就行了
return nums[left] == target ? left:-1
3.查找终止条件
什么时候停止呢，当然是找到值后停止搜索，看代码
if (nums[mid]==target)
return mid;
4.mid的加减
先看代码
else if (nums[mid]<target)
left=mid+1;
else if (nums[mid] > target)
right = mid-1;
因为搜索区间都为闭区间，所以当mid不是target对应的值时，我们就需要将区间缩小，向左还是向右呢？
nums[mid]值大于target时，当然是left加1，区间向右缩减。
要点
若要使用这个代码，还要再加一行代码，要将数组排序，然后再来查询。