【Java】简明--二分搜索

前言

题目1.分析2.while终止条件3.查找终止条件4.mid的加减要点

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

我先引入一个题，这个题很简单，即搜索一个数，存在则返回索引，不存在则-1。

import java.util.*;


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) 
                right = mid-1;
            
        }
        return -1;
    }
}

我们初始化的right是nums.length-1，是数组最后一个元素的索引，索引while循环中的条件是<=而不是<。

索引这两种方式是有不同的功能的：

nums.length-1
这种表达形式相当于选择的区间都是闭区间，类似于

[left, right]

nums.length
这种表达形式相当于选择的区间左闭右开区间，类似于

[left, right)

为什么右开呢？

因为索引的大小为nums.length的值是越界的
如上图，数组的长度为5，已经超过了索引值

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 再来看这种情况，终止的条件为left=right，也就是区间为 [left,right] 的形式

再举列子：
[3,3]的区间，这个区间的可取值为3，但是循环的结束条件为left

return nums[left] == target ? left:-1

什么时候停止呢，当然是找到值后停止搜索，看代码

if (nums[mid]==target)
	return mid;

先看代码

else if (nums[mid] target) 
	right = mid-1;

因为搜索区间都为闭区间，所以当mid不是target对应的值时，我们就需要将区间缩小，向左还是向右呢？

nums[mid]值大于target时，当然是left加1，区间向右缩减。

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