二分查找算法的原理与边界问题

电玩女神 2024-03-27 03:55 139阅读 0赞

## 1.二分查找动态图 ##

![20210313090428873.gif_pic_center][]

## 2.二分查找的基础了解 ##

*  概念：

> 在计算机科学中，**二分搜索**（英语：binary search），也称**折半搜索**（英语：half-interval search）、**对数搜索**（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索[算法][Link 1]。[搜索][Link 2]过程从[数组][Link 3]的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

*  代码重难点：

1.区间的边界符号，到底取闭区间还是开区间，如right=middle还是middle-1

2.while（left right）循环中取=还是不取

## 3.代码具体实现 ##

*  \[left,right\]
 *  \[left,right)
 *  (left,right\]

解析\[left,right\]为例,求目的target

![18326c70b7bf461cad158bc5d194ff74.png][]

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

1.因为是\[left,right\]左闭右闭，所以这里的while取=是合法区间，是可以取的

> while(left<=right)

2.这里计算middle的时候要注意right+left可能会超出最大数字，因此为了避免这种情况，要使用下面这种方式计算

> middle = left + (right-left)>>1;

3.这里的right取middle-1是因为条件判断出了nums\[middle\]已经是比target大，因此，就不需要再包含middle

> if(nums\[middle\]>target) right = middle-1

\[left,right)

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

1.因为是\[left,right)左闭右开，所以这里的while取=是不合法区间，因为当都为1的时候，就是\[1,1)不合理

> while(left<=right)

2.这里的right取middle是因为\[left,right)，右边是)没有取right这个值，并判断出了nums\[middle\]已经是比target大，因此下一个搜索的区间（即左区间0到middle）就不包括middle，就需要再包含middle

> if(nums\[middle\]>target) right = middle-1

参考文章

[(2条消息) 查找算法：二分查找\_weixin\_47406709的博客-CSDN博客\_二分查找][2_ _weixin_47406709_-CSDN]

[20210313090428873.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/30e53dcdb13a4ffe90b58c060fdd429a.png
[Link 1]: https://baike.baidu.com/item/%E7%AE%97%E6%B3%95?fromModule=lemma_inlink
[Link 2]: https://baike.baidu.com/item/%E6%90%9C%E7%B4%A2/1806?fromModule=lemma_inlink
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84/3794097?fromModule=lemma_inlink
[18326c70b7bf461cad158bc5d194ff74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/951120c599a94c5e874278ffbee1109f.png
[2_ _weixin_47406709_-CSDN]: https://blog.csdn.net/weixin_47406709/article/details/125660759?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167557202916782428612460%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=167557202916782428612460&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-125660759-null-null.142%5Ev73%5Epc_search_v2,201%5Ev4%5Eadd_ask,239%5Ev1%5Einsert_chatgpt&utm_term=%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187