算法-查找-二分法

二分法

​ 写二分法时首先要看要搜索的区间，一般来讲区间有左闭右开，左闭右闭两种，这个区间决定着while时left是小于等于还是小于。

左闭右开

[ left, right )，也就是这样的搜索区间，先挂代码

class Solution {
    public int search(int[] nums, int target) {
        if(target<nums[0]||target>nums[nums.length-1])return -1;
        int left=0,right=nums.length;
        while(left<right){
            int middle=(left+right)/2;
            if(nums[middle]<target){
                left=middle+1;
            }else if(nums[middle]>target){
                right=middle;
            }else{
                return middle;
            }
        }
        return -1;
    }
}

首先搜索区间里要是一个有序的数组，然后才能用二分，查找流程

1. 比较目标值是否在这个搜索区间，比最小的小比最大的大就不再，直接return
2. 规定区间，left，right，由你想要的搜索区间决定right的值，right=nums.length时就代表这个区间是右开的，因为right的值访问不到
3. 然后while循环，循环条件这里，根据你的区间决定，这里如果是<=就是不和法的，由第二步知，right访问不到，也就是left<=right这里left不能等于right 如：[1,1)，这里右边的1是取不到的，所以只能是小于
4. 设置中间值middle，这里left直接加right可能会由溢出的风险，可以采用下面这种写法

int middle=left+(right-left)/2;

1. 然后将中间值与目标值进行比较，如果大于就更新，right的值，这里right为什么要等于middle呢？ middle不是已经比较过了吗？ 原因就是我们的区间里right的值取不到，所以right可以直接更新为middle
2. 根据第五步，如果小于，left=middle+1，这里为什么不是middle，应该不用解释了，因为这里left可以取到，middle已经比较过了，就不用放到这次的搜索区间里了
3. 最后一种情况就是等于，可以直接return middle值，也就是目标值的下标
4. 如果循环结束，还没找到，可以直接ruturn 象征没找到的数字

左闭右闭

[ left，right ]，这样的搜索区间，以下是代码

class Solution {
    public int search(int[] nums, int target) {
        if(target<nums[0]||target>nums[nums.length-1])return -1;
        int left=0,right=nums.length-1;
        while(left<=right){
            int middle=(left+right)/2;
            if(nums[middle]<target){
                left=middle+1;
            }else if(nums[middle]>target){
                right=middle-1;
            }else{
                return middle;
            }
        }
        return -1;
    }
}

与左闭右开大部分步骤一致，以下是不同

int left=0,right=nums.length-1;

这里right的值为length-1，正好是数组最后一个的下标，可以访问到

while(left<=right)

left可以等于right，因为区间是左闭右闭，是合法的，

if(nums[middle]>target){
                right=middle-1;
            }

这里middle进行了减一，这里与上面第六步的原因一致