Leetcode刷题笔记：二分查找算法

系统管理员 2023-10-01 12:17 27阅读 0赞

### 题目：二分查找 ###

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用 O(log n) 完成搜索任务。它的基本思想是：（这里假设数组元素呈升序排列且不重复）将n个元素分成个数大致相同的两半，取a\[n/2\]与欲查找的x作比较，如果x=a\[n/2\]则找到x，算法终止；如果x < a \[n/2\]，则我们只要在数组a的左半部继续搜索x；如果x > a\[n/2\]，则我们只要在数组a的右 半部继续搜索 x。

通俗讲，就是在有序数组中，寻找一个目标值的步骤为：定好左右边界值下标 left 与 right ，从而确定中间值下标，进而从中间开始排除目标值是否存在于数组中，最后在确认左右区间是否存在目标值，不断循环直至找到目标值或结束循环。

[LeetCode题目链接][LeetCode]

#### 题目描述 ####

给定一个 n 个元素***有序的（升序）整型数组*** nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

#### 测试用例 ####

示例 1:  
输入: nums = \[-1,0,3,5,9,12\], target = 9  
输出: 4  
解释: 9 出现在 nums 中并且下标为 4

示例 2:  
输入: nums = \[-1,0,3,5,9,12\], target = 2  
输出: -1  
解释: 2 不存在 nums 中因此返回 -1

#### 提示 ####

*  你可以假设 nums 中的所有元素是不重复的。
 *  n 将在 \[1, 10000\]之间。
 *  nums 的每个元素都将在 \[-9999, 9999\]之间。

这类型数组为有序数组并且为升序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件。

注意：无序数组无法使用二分法、降序与升序数组大小关系相反，**中间索引值注意内存溢出**。

#### 为什么中间值取值需要注意存在内存溢出呢？ ####

如果存在左边界值 int left ，右边界值 int right ，取它们的中间值，第一时间想到的就是 (left+right)/2 ，而这就将发生内存溢出，由于 int 数据类型存在最大最小值，假设，right值等于最大值，left+right 的值就大于 int 的最大值，发生内存溢出。  
解决方案：使用 **left+((right-left)/2)**,将每个过程所得值都限制在最大值内。

right-left = 数组长度 < maxInt
    (right-left)/2 = middle长度 < maxInt
    left<left+((right-left)/2) < right < maxInt
    left+((right-left)/2) < right < maxInt

不再出现内存溢出。

#### 二分法的两种做法 ####

二分法就区间的取法可分为两种做法：

*  左闭右开，即 \[left,right)  
    每次循环条件为 left< right ，当 nums\[middle\] > target 时，迭代体为 right = middle，反之，left = middle+1。
 *  左右全闭，即 \[left,right\]  
    每次循环条件为 left<= right ，当 nums\[middle\] > target 时，迭代体为 right = middle-1，反之，left = middle+1。

此处所提到的左右全闭与左闭右开是边界值下标 left 与 right 相对于目标值 target 而言的取值区间。  
对于这两种做法，由于区间不同，着重认识每次循环后，right 的取值问题之间的区别，即边界问题的处理方法。

#### Java 程序代码 ####

对于本题如若还需其他语言版本的解题代码，请参照代码随想录中的相关内容，链接已放置文末。

##### 边界逻辑代码模板 #####

不能拘泥于模板的使用，否则，可能存在不合时宜地题目优化问题，甚至解决不了问题，学会根据题目需求灵活解决问题才是王道。

*  左右全闭

class Solution {
        
        public int searchInsert(int[] nums, int target) {
        
            int left = 0, right = nums.length - 1;
            while(left <= right) {
         
                int mid = (left + right) / 2;
                if(nums[mid] == target) {
         
                    // 相关逻辑
                } else if(nums[mid] < target) {
        
                    left = mid + 1; 
                } else {
        
                    right = mid - 1; 
                }
            }
            // 相关返回值
            return 0;
        }
    }

*  左闭右开

class Solution {
        
        public int searchInsert(int[] nums, int target) {
        
            int left = 0, right = nums.length; 
            while(left < right) {
         
                int mid = (left + right) / 2; 
                if(nums[mid] == target) {
        
                    // 相关逻辑
                } else if(nums[mid] < target) {
        
                    left = mid + 1; 
                } else {
        
                    right = mid; 
                }
            }
            // 相关返回值
            return 0;
        }
    }

##### 解题代码 #####

*  左右全闭

class Solution {
        
        public int search(int[] nums, int target) {
        
            int left=0;
            int right=nums.length-1;
            
            if(nums[left]>target | nums[right]<target){
        
                return -1;
            }
            else{
        
                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;
        }
    }

*  左闭右开

class Solution {
        
        public int search(int[] nums, int target) {
        
            int left=0;
            int right=nums.length-1;
            if(nums[left]>target | nums[right]<target){
        
                return -1;
            }
            else{
        
                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;
        }
    }

#### 相关链接 ####

##### 相关其他题目 (LeetCode 链接) #####

*  [搜索插入位置][Link 1]
 *  [在排序数组中查找元素的第一个和最后一个位置][Link 2]

##### 参考文章 #####

*  [二分搜索代码模板来源：画解算法：35. 搜索插入位置][35.]
 *  [代码随心录：数组-二分查找][-]

![求点赞转发][format_png]

[LeetCode]: https://leetcode-cn.com/problems/binary-search/
[Link 1]: https://leetcode-cn.com/problems/search-insert-position/
[Link 2]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[35.]: https://leetcode-cn.com/problems/search-insert-position/solution/hua-jie-suan-fa-35-sou-suo-cha-ru-wei-zhi-by-guanp/
[-]: https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
[format_png]: https://img-blog.csdnimg.cn/img_convert/228f0abec8314807089e308e8e5caafc.webp?x-oss-process=image/format,png