前言

在做算法题时，有的时候会用到二分搜索，我自己总结一下其规律，来和大家分享，开整。

题目

我先引入一个题，这个题很简单，即搜索一个数，存在则返回索引，不存在则-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，区间向右缩减。

要点

若要使用这个代码，还要再加一行代码，要将数组排序，然后再来查询。