二分查找算法：穿越算法迷宫的指南

✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

目录

前言

一.  二分查找算法介绍

二 二分查找的题目解析

2.1 二分查找

2.2 在排序数组中查找元素的第一个位置和最后一个位置

2.3 搜索插入位置 

2.4 x的平方根 

 2.5 山峰数组峰顶的索引

 2.6 寻找峰值

2.7 寻找旋转数组中的最小值 

2.8 点名 

 三. 二分算法总结+模板

总结

前言

本篇详细介绍了二分查找算法的使用，让使用者了解二分查找，而不是仅仅停留在表面， 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

一.  二分查找算法介绍

二. 二分查找的题目解析

开始之前可以去总结部分被去看看模板，再结合题目理解

2.1 二分查找

704. 二分查找 – 力扣（LeetCode）

 思路：（模版1）正常的二分查找策略

class Solution {
public:
    int search(vector& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left  target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }
};

2.2 在排序数组中查找元素的第一个位置和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 – 力扣（LeetCode）

思路：找第一个，用左区间端点查找（模版2），找最后一个，用右端点区间查找（模版3） 

class Solution {
public:
    vector searchRange(vector& nums, int target) {
        //处理边界情况
        if(nums.size() == 0) return {-1,-1};
        int left = 0;
        int right = nums.size()-1;
        int first = 0;
        //  1.二分左端点
        while(left= target)
            {
                right = mid;
            }
            else
            {
                left = mid +1;
            }
        }
        //判断是否有结果
        if(nums[left] != target) return {-1,-1};
        else first = left;  //标记一下左端点
 
        //  2.二分右端点
        left = 0,right = nums.size()-1;
        while(left<right)
        {
            int mid = (right - left+1)/2+left;
            if(nums[mid] <= target)
            {
                left = mid;
            }
            else
            {
                right = mid -1;
            }
        }
        
        return {first,right};
    }
};

2.3 搜索插入位置 

35. 搜索插入位置 – 力扣（LeetCode） 

 思路：左端区间查找 （右区间查找也行

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int left = 0, right = nums.size()-1;
        if(nums[right]<target) return right + 1;
        while(left =target) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

2.4 x的平方根 

69. x 的平方根 – 力扣（LeetCode） 

思路：右端区间二分查找法 

class Solution {
public:
    int mySqrt(int x) {
        if(x == 0) return 0; //处理边界情况
        int left = 1, right = x;
        while(left<right)
        {
            long long mid = (right - left + 1) /2+left; //防溢出
            if(mid*mid<=x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

 2.5 山峰数组峰顶的索引

852. 山脉数组的峰顶索引 – 力扣（LeetCode） 

思路：左或右端区间查找

class Solution {
public:
    int peakIndexInMountainArray(vector& arr) {
        int left = 1 ,right = arr.size()- 2;
        while(left arr[mid-1]) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

 2.6 寻找峰值

162. 寻找峰值 – 力扣（LeetCode） 

 思路：左或右端点区间查找

 右区间：

class Solution {
public:
    int findPeakElement(vector& nums) {
        int left = 0, right = nums.size()-1;
        while(left < right)
        {
            int mid = (right - left) / 2 + left;
            if(nums[mid]<nums[mid+1]) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

2.7 寻找旋转数组中的最小值 

153. 寻找旋转排序数组中的最小值 – 力扣（LeetCode）

思路：左区间端点查找法 

class Solution {
public:
    int findMin(vector& nums) {
        int left = 0, right = nums.size()-1;
        int n = nums.size();
        while(leftnums[n-1]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
};

2.8 点名 

LCR 173. 点名 – 力扣（LeetCode）

 思路：左区间查找

class Solution {
public:
    int takeAttendance(vector& records) {
        int left = 0, right = records.size()-1;
        while(left<right)
        {
            int mid = (right - left)/2+left;
            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        //处理细节问题:最后一个位置缺少
        return records[left] == left ? left+1 : left;
    }
};

 三. 二分算法总结+模板

二分查找的策略基本上都是去找一个数，对应的有三种模版：正常的二分查找、左区间端点查找、右区间端点查找。其中正常的二分查找局限性比较大，必须得是升序且限制条件较多，大多数情况下不符合题意。最常用的就是左区间端点（关键是left会大跳跃，且目标位置在较大值区间的左边）和右区间端点法（关键是right会大跳跃，且目标位置在较小值区间的右边）。 

图from：算法思想总结：二分查找算法-CSDN博客 

总结

✨✨✨各位读友，本篇分享到内容是否更好的让你理解二分查找算法，如果对你有帮助给个👍赞鼓励一下吧！！
🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！