二分查找说“简单”又“不简单”

深碍√TFBOYSˉ_ 2023-07-22 07:00 29阅读 0赞

### 目录 ###

*  1.二分查找算法
 *   *  使用前提
     *  原理
 *  2.二分查找模板
 *   *  非递归模板
     *  递归模板
 *  3.二分查找细节
 *   *  使用场景
     *  while循环条件
     *  为什么 left = mid + 1，right = mid - 1？
     *  为什么 left = mid + 1，right = mid ？
     *  为什么最后返回 left 而不是 right？
 *  4.小小总结
 *   *  二分查找法的缺陷
     *  小小建议

**二分查找也叫折半查找，学过的人都会说二分查找思路很简单，可以使用模板，是有规律可循的，事实确实是这样的，也就是所谓的“简单”，但是它真的“简单”吗？**

**为什么又说二分查找“不简单”？二分查找“不简单”在查找的边界控制、循环控制，深入细节，比如while循环中条件是否应该带等号，mid 是否应该加一等等，这都需要去思考和测试才能找到答案，细节是魔鬼！**

# 1.二分查找算法 #

为什么叫做二分查找？顾名思义需要“二分”，也就是将有序的数据分成两部分来完成查找。

## 使用前提 ##

*  必须为顺序存储
 *  存储在数组中（**链表不可以**）

Tips:至于数组顺序递增排列还是递减排列，数组中是否存在相同的元素都不要紧。不过一般情况，还是希望并假设数组是递增排列，数组中的元素互不相同。

## 原理 ##

*  将有序数组分为三部分：左部分，中间值mid，右部分，即定义边界left与right，计算mid
 *  首先将要查找的目标值target与中间值进行对比，由于是有序数组，就会有三种比较结果：  
    1.mid==target，如果是查找target，可以直接返回索引mid；  
    2.mid<target，说明target存在于右区间，缩小区间至右区间  
    3.mid>target，说明target存在于左区间，缩小区间至左区间
 *  依次递归，直到查找到target或者不存在target  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]

# 2.二分查找模板 #

## 非递归模板 ##

public int binarySearch(int[] nums,int target){
        
    	int left = 0, 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 {
               //左区间查找
                    right = mid - 1; // 注意
                }
            }
            // 相关返回值
            return -1;
    }

## 递归模板 ##

public int binarySearch(int[] nums,int target,int left,int right) {
        
    		if(left > right) //递归终止条件
    			return -1;
    		int mid = left + (right-left)/2;
    		if(nums[mid] == target) //递归终止条件
    			return mid;
    		else if(nums[mid] > target) //查找左区间
    			return binarySearch(nums, target, left, mid-1);
    		else					//查找右区间
    			return binarySearch(nums, target, mid+1, right);
    	}

Tips：计算 mid 时需要技巧防止溢出，建议写成: mid = left + (right - left) / 2；  
如果right-left也有可能涉及到溢出的时候，使用mid=(left+right)>>>1（无符号右移）  
查找不到的数据均返回了-1，可以根据具体题意进行修改

# 3.二分查找细节 #

思路很简单，细节是魔鬼。

## 使用场景 ##

*  **有序数组中查找一个数（存在或不存在）** [35. 搜索插入位置][35.]
 *  **有序数组中查找边界（左边界或右边界）**，也就是说在有序数组中找到“正好大于（小于）目标数”的那个数 [278. 第一个错误的版本][278.]
 *  **有序数组中查找区域**，假如存在重复数据，而数组依然有序，那么还是可以用二分查找法判别目标数是否存在，希望知道目标值有多少个，也就是目标值所存在的区域 [34. 在排序数组中查找元素的第一个和最后一个位置][34.]
 *  **将有序数组通过旋转得到的数组，也就是“轮转后的有序数组（Rotated Sorted Array）”**，依旧可以使用二分查找，例如：｛6,9,10,12,0,2,3,4｝[33. 搜索旋转排序数组][33.]

Tips：超链接均是LeetCode中二分查找所对应的使用场景，可以根据具体的题目来深入学习和理解

## while循环条件 ##

拿非递归模板来说，**循环条件是由left与right边界的确定而确定的**，循环条件指的是while语句中的判断条件，有两种可能：

*  **`int left = 0 ; right = nums.length;`对应的循环条件是`while(left < right)`**  
    定义了right=nums.length，实际上nums\[nums.length\]这个值是不存在的，所以这个区间可以理解为一个**左闭右开的区间 \[left，right)**，把这个区间叫做 **搜索区间**；  
    当使用二分查找的时候，当查找不到目标值的时候while条件应该停止进行返回， **那什么时候查找不到目标值呢？** 当搜索区间为空的时候，也就是说没有符合要求的数据来进行遍历查找了， **搜索空间又何时为空？**  
    `while(left < right)`的终止条件是 left == right，写成区间的形式为 \[right，right)，若right=6，搜索区间为\[6，6),即搜索区间是空的，即没有数据可以查找进行返回，证明while条件是正确的。  
     如果循环条件写成`while(left <= right)`呢？终止条件是left=right+1,搜索区间为\[right+1，right)，转换为(right,right+1\],此时带入right=6，搜索区间为(6，7\]，此时搜索区间不为空，漏掉了数字7，但是while条件却不成立直接返回，那么程序自然就出错了!
 *  **`int left = 0 ; right = nums.length - 1;`对应的循环条件是`while(left <= right)`**  
    定义了right = nums.length-1，这个索引对应的值nums\[nums.length-1\]是可以取到的，所以**搜索区间是一个完全的闭区间\[left,right\]**；  
    `while(left<=right)`对应的终止条件是left=right+1，搜索区间为\[right+1，right\]，带入right=6，搜索区间为\[7，6\]，搜索区间为空，这个区间不存在符合的数据，while循环可以正常终止，程序运行正确！  
    如果循环条件写成`while(left < right)`呢？终止条件为right==left，搜索区间为\[right，right\]，带入right=6，搜索区间为\[6，6\]，搜索区间不为空，但是while循环却终止了，说明漏掉了数字6，程序就可能出现错误了！

## 为什么 left = mid + 1，right = mid - 1？ ##

如果使用场景是在有序数组中查找一个数，那么当发现索引 mid 不是要找的 target 时，如何确定下一步的搜索区间呢？  
**当然是去搜索 \[left, mid - 1\] 或者 \[mid + 1, right\] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。**

## 为什么 left = mid + 1，right = mid ？ ##

如果使用场景是查询左侧边界，那么当nums\[mid\]==target的时候，并不是第一时间返回mid索引，因为需要寻找的是左侧的边界，也就是比target小的数据，有可能你所要查找的nums\[\]中就不存在target，当nums\[mid\]==target的时候，接下来的搜索区间是什么呢？  
**一定是\[left，mid\]与\[mid+1，right\]，因为根据题意无法去排除掉mid！**

Tips:同理，如果使用场景是查询右侧边界，应该是left=mid，right=mid-1，对应搜索区间为\[left，mid-1\]与\[mid，right\]

**二分查找查询右边界**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]

//二分查找查询右边界
    public int binarySearchRight(int[] nums,int target){
        
    	int left = 0, right = nums.length - 1; // 闭区间
            while(left <= right) {
         // 边界决定循环条件
                int mid = left + (right - left) / 2; // 防止整型溢出
                if(nums[mid] > target) {
         // 左区间查找
                    // 相关逻辑
                    right = mid;
                } else  // 右区间查找
                    left = mid + 1; 
            }
            // 相关返回值
            return left;//返回left与right均可
    }

Tips：查询左边界或右边界实现都是找严格界限，也就是要大于或者小于。如果要找松散界限，也就是找到大于等于或者小于等于的值（即包含自身），只需要稍作修改即可

在与中间值的比较中加上等号：

nums[mid] > target 改为 nums[mid] >= target

## 为什么最后返回 left 而不是 right？ ##

返回left和right都是一样的，因为 while 终止的条件是 left == right

# 4.小小总结 #

## 二分查找法的缺陷 ##

二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：  
必须有序，我们很难保证使用的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：必须是数组数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。  
解决这些缺陷问题更好的方法应该是使用[二分搜索树][Link 1]了，最好自然是自平衡二叉查找树了，自能高效的（O(nlogn)）构建有序元素集合，又能如同二分查找法一样快速（O(logn)）的搜寻目标数。

## 小小建议 ##

**二分查找模板需要记忆，其中提到了几道典型的LeetCode，熟悉使用场景，把握每个场景所对应细节，多思考再回来看，二分查找就可以说“简单”了！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: /images/20230528/1797b99a25cb4f3281226d6f84ea655d.png
[35.]: https://leetcode-cn.com/problems/search-insert-position/
[278.]: https://leetcode-cn.com/problems/first-bad-version/
[34.]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[33.]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]: /images/20230528/04891ceb3cdd44ba93fc121dda8d7408.png
[Link 1]: https://blog.csdn.net/weixin_44190113/article/details/104072362