本文主要是介绍2021-10-20：二分查找，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

二分查找

leetcode题目链接：https://leetcode-cn.com/problems/binary-search/

第一种解法（也是最常见的解法）：但只针对当前题目

1. 左闭右闭：right=nums.lenght-1；
2. 左闭右开：right=nums.lenght；
   上面右边界的开或关决定了while循环中的等号是否支持，和right=middle+1；还是right=middle。边界值很重要（关键是要保证能遍历到数组中的每一个值与nums[middle]进行比对）

public int search(int[] nums, int target) {
        int left=0;
        //区间左闭右闭方法 []
        //int right=nums.length-1;
        // while(left<=right){
        //     int middle=left+(right-left)/2;
        //     if (nums[middle]<target){
        //         left=middle+1;
        //     }else if(nums[middle]>target){
        //         right=middle-1;
        //     }else{
        //         return middle;
        //     }
        // }
        // return -1;
        
        //区间左闭右开方法 [ )
        int right=nums.length;
        while(left<right){
            int middle=left+(right-left)/2;
            if (nums[middle]<target){
                left=middle+1;
            }else if(nums[middle]>target){
                right=middle;
            }else{
                return middle;
            }
        }
        return -1;
    }

第二方法：算法摘自UP主《五点七边》链接如下：

https://www.bilibili.com/video/BV1d54y1q7k7?spm_id_from=333.999.0.0

先附上具体算法和不同的问题场景：

最初本人去调的时候也是觉得逻辑很简单，但具体实现的时候就是有部分用例不通过。无奈来B站找找好的老师。最先接触到的是第一种左右边界的方法，理解起来就有点晕晕的。后来又看到了五点七边老师的视频。刚开始看的时候还带有右边界是开还是关的思维，就半天没理解五点七边的逻辑。后来看了两遍自己拿个例子推了一遍，感觉自己明白了，哈哈哈。

为啥要划分蓝红两个区域呢，通过最后视频中给出的例子的答案可以反推出来。我们的最终目的是要依据问题场景确定返回 left 还是right 。看完觉得我看着已经知道全部数组元素的成员还是蛮简单找出蓝红边界的条件的。可现实是我不知道数组长啥样。嗯！再观察一下例子我们就可以知道了。

以本力扣题为例举个栗子：

假如target为X。题目中已说明元素不会重复，且target不一定在数组中。
那么我们的isBlue条件可以确定为第一个小于target的元素，即nums[middle]<target; 退出while循环返回的值为right。那么nums[right]要么等于target，要么大于target。我们再判断一下nums[right]是否对等于target，如果等于就返回right，否则就返回-1.
但是代码中有一个点需要注意（也是提交代码时候才发现）：当数组中所有的元素为蓝色区域时。退出while循环返回的right值为N，而数组元素的小标为N-1；此时如果判断nums[right]target时，就会报告数组越界。解决办法是加一个判断，如代码中所示：if(rightnums.length||nums[right]!=target)。

public int search(int[] nums, int target) {
        // 五点七边的方法
        int left =-1;
        int right =nums.length;
        while(left+1!=right){
            int middle=left+((right-left)/2);
            if (nums[middle]<target){
                left=middle;
            }else{right=middle;}
        }
        if(right==nums.length||nums[right]!=target){
            return -1;
        }else{
            return right;
            }
    }

这篇关于2021-10-20：二分查找的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！