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

码农世界 2024-06-12 后端 95 次浏览 0个评论

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

前言

一. 二分查找算法介绍

二二分查找的题目解析

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 <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > 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 
2.3 搜索插入位置  
35. 搜索插入位置 - 力扣（LeetCode）  
 思路：左端区间查找 （右区间查找也行 
class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int left = 0, right = nums.size()-1;
        if(nums[right]=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 
 2.5 山峰数组峰顶的索引 
852. 山脉数组的峰顶索引 - 力扣（LeetCode）  
 
思路：左或右端区间查找 
 
class Solution {
public:
    int peakIndexInMountainArray(vector& arr) {
        int left = 1 ,right = arr.size()- 2;
        while(left < right)
        {
            int mid = (right - left + 1) / 2 + left;
            if(arr[mid]>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] 
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 
 三. 二分算法总结+模板 
二分查找的策略基本上都是去找一个数，对应的有三种模版：正常的二分查找、左区间端点查找、右区间端点查找。其中正常的二分查找局限性比较大，必须得是升序且限制条件较多，大多数情况下不符合题意。最常用的就是左区间端点（关键是left会大跳跃，且目标位置在较大值区间的左边）和右区间端点法（关键是right会大跳跃，且目标位置在较小值区间的右边）。  
 
 
 
图from：算法思想总结：二分查找算法-CSDN博客  
 
 
总结 
✨✨✨各位读友，本篇分享到内容是否更好的让你理解二分查找算法，如果对你有帮助给个👍赞鼓励一下吧！！
🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！