【算法】二分查找

文章目录

• 引言
• 一、二分查找
• 二、查找元素的第一个和最后一个位置
• 三、x的平方根
• 四、搜索插入位置
• 五、山脉数组的峰顶索引
• 六、寻找峰值
• 七、寻找旋转数组中的最小值
• 八、寻找旋转数组中的最小值 ||
• 总结

引言

二分查找，实际上也是左右双指针的变形，本质是利用数组的二段性进行查找。总共有三个模板：朴素二分、左边界二分、右边界二分

一、二分查找

思路：

1. 这道题就是标准的朴素二分，也是最简单最基础的二分
2. 循环条件：left <= right
3. 求中点（两种方法都可以）：
   • int mid = left + (right-left)/2;//求左中点
   • int mid = left + (right-left+1)/2;//求右中点
4. 上述求中点方法，可以防止溢出

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

二、查找元素的第一个和最后一个位置

思路：

1. 本题便用到了左边界二分和右边界二分
2. 循环条件：left < right（注意：判断等于会死循环）
3. 左边界二分：int mid = left + (right-left)/2;//求左中点
4. 右边界二分：int mid = left + (right-left+1)/2;//求右中点
5. 出循环后，还要再判断当前位置的值是否为target

class Solution
{
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        if(nums.size() == 0) return {-1, -1};
        int begin = -1, end = -1;

        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right-left)/2;
            if(nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        if(nums[left] == target) begin = left;

        left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right-left+1)/2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        if(nums[left] == target) end = left;

        return {begin, end};
    }
};

三、x的平方根

思路：

1. 右边界二分
2. 注意mid*mid数值太大，int 会溢出，所以改成long long

class Solution
{
public:
    int mySqrt(int x)
    {
        int left = 1, right = x;
        while(left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return right;
    }
};

四、搜索插入位置

思路：

• 左边界二分

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

五、山脉数组的峰顶索引

思路：

• 左边界二分（右边界也可以）

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

六、寻找峰值

思路：

• 左边界二分（右边界也可以）

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

七、寻找旋转数组中的最小值

思路：

1. 每次选取right指向的值，作为比较的基准值
2. 左边界二分

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

八、寻找旋转数组中的最小值 ||

思路：

1. 这题是上题的变形，主要改变是存在重复元素
2. 还是左边界二分，不过在 nums[mid] == nums[right] 时，- -right 即可

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

总结

二分查找，是一种十分高效的查找算法，时间复杂度为O(logN)，在数组具有二段性时便可应用。

同时，只要掌握并理解了二分的模板，它便是最简单、最容易的一类题型~