算法魅力-二分查找实战

前言

算法定义

朴素二分模版

二分查找

二分的边界查找

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

暴力算法

二分查找

边界查找分析

山峰数组的峰顶

暴力枚举

二分查找

搜索旋转排序数组中的最小值（medium）

二分查找

结束语

前言

在前面我们学习了双指针，以及其中诞生的分支滑动窗口，接下来我们将探讨其另外一个“兄弟”-二分查找。本质上也是用左右两个指针。

这个算法的前提是我们数据是有序排列的，这里的有序并不只是单纯的有序，有时候根据数据的排列我们可以将数据划分为两个区间，可以简称为二段性，（两段区间是有序的）且根据问题选择合适的二分思路，二分算法有基础的套用也有进阶的实现。

算法定义

二分查找算法（Binary Search Algorithm）是一种在有序数组中查找特定元素的搜索算法。其基本思想是通过不断将搜索区间缩小一半来查找目标值。以下是二分查找算法的步骤：

首先确定搜索区间的起始位置（left）和结束位置（right）。
计算中间位置（mid），通常是(left + right) / 2，为了避免溢出也可以写成left + (right - left) / 2。有时候也写成 left + (right - left+1) / 2，两者区别就是在偶数个数据时，一个是取左边，一个是取靠中间右边。可以理解成向下或者向上取整。
比较中间位置的元素与目标值：
- 如果中间位置的元素等于目标值，则搜索成功，返回中间位置的索引。
- 如果中间位置的元素小于目标值，则将搜索区间的起始位置设置为mid + 1，因为目标值必定在右侧区间。
- 如果中间位置的元素大于目标值，则将搜索区间的结束位置设置为mid - 1，因为目标值必定在左侧区间。
重复步骤2和3，直到找到目标值或者搜索区间为空（即left > right）。

如果整个数组中没有找到目标值，则返回一个特殊值（如-1）表示未找到。

朴素二分模版

#include <vector>

int binarySearch(const std::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) {
            return mid; // 找到目标值，返回索引
        } else if (nums[mid] < target) {
            left = mid + 1; // 在右侧区间继续查找
        } else {
            right = mid - 1; // 在左侧区间继续查找
        }
    }
    return -1; // 未找到目标值
}

二分查找

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

本题可以通过暴力枚举，通过将数组的数据与目标值进行比较，相等就返回下标，不存在就返回-1.

本题也可以直接就二分查找，就像题目标题一样。

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;
    }

};

二分的边界查找

有效利用数据的二段性

下面我们将通过一道题来引入进阶的二分。

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

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

暴力算法

这道题我们同样可以通过遍历数据来求得左右位置，一个从左边开始查找，一个从右边开始查找，相等就保存并返回到数据中，代码实现也很简单。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left=-1,right=-1;
        int n=nums.size();
        for(int i=0;i<n;i++){
            if(nums[i]==target){
            left=i;
            break;
            }
        }
        for(int j=n-1;j>=0;j--){
            if(nums[j]==target){
                right=j;
                break;
            }
        }
       return{left,right};
    }
};

但是这道题让我们设置O(logn)的时间复杂度，同样是查找，故我们可以采用二分查找的思路。

只不过这里要左右两个值，理所当然采用两次二分查找，本质上这道题就是进行左右边界查找。

二分查找

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

边界查找分析

方便叙述，用 x 表示该元素， resLeft 表示左边界， resRight 表示右边界。

左边界查找

寻找左边界思路

左边区间 [left, resLeft - 1] 都是小于 x 的；

右边区间（包括左边界） [resLeft, right] 都是大于等于 x 的；

因此，关于 mid 的落点，我们可以分为下面两种情况：

当mid 落在 [left, resLeft - 1] 区间的时候，也就是 arr[mid] < target 。说明 [left, mid] 都是可以舍去的，此时更新 left 到 mid + 1 的位置，继续在 [mid + 1, right] 上寻找左边界；

当 mid 落在 [resLeft， right] 的区间的时候，也就是 arr[mid] >= target 。

说明 [mid + 1, right] （因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时更新 right 到 mid 的位置，继续在 [left, mid] 上寻找左边界；

注意：这面找中间元素需要向下取整。

因为后续移动左右指针的时候：

左指针： left = mid + 1 ，是会向后移动的，因此区间是会缩小的；

右指针： right = mid ，可能会原地踏步（比如：如果向上取整的话，如果剩下 1,2 两个元

素， left == 1 ， right == 2 ， mid == 2 。更新区间之后， left，right，mid 的

值没有改变，就会陷入死循环）。

因此一定要注意，当 right = mid 的时候，要向下取整。

寻找右边界思路

用 resRight 表示右边界；

注意到右边界的特点：左边区间（包括右边界） [left, resRight] 都是小于等于 x 的；

右边区间 [resRight+ 1, right] 都是大于 x 的；

关于 mid 的落点，可以分为下面两种情况：

当mid 落在 [left, resRight] 区间的时候，说明 [left, mid - 1] （ mid 不可以舍去，因为有可能是最终结果）都是可以舍去的，此时更新 left 到 mid

的位置；

当 mid 落在 [resRight+ 1, right] 的区间的时候，说明 [mid, right] 内的元素是可以舍去的，此时更新 right 到 mid - 1 的位置；

注意：这里找中间元素需要向上取整。

因为后续移动左右指针的时候：

左指针： left = mid ，可能会原地踏步（比如：如果向下取整的话，如果剩下 1,2 两个元

素， left == 1， right == 2，mid == 1 。更新区间之后， left，right，mid 的值没有改变，就会陷入死循环）。

右指针： right = mid - 1 ，是会向前移动的，因此区间是会缩小的；

综上所述：

当选择两段式的模板时：

在求 mid 的时候，只有 right - 1 的情况下，才会向上取整（也就是 +1 取中间数）

山峰数组的峰顶

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

暴力枚举

峰顶的特点：⽐两侧的元素都要⼤。

因此，我们可以遍历数组内的每⼀个元素，找到某⼀个元素⽐两边的元素⼤即可。

class Solution {
public:
 int peakIndexInMountainArray(vector<int>& arr) {
 int n = arr.size();
 // 遍历数组内每⼀个元素，直到找到峰顶
 for (int i = 1; i < n - 1; i++) 
 // 峰顶满⾜的条件
 if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
 return i; 
 // 为了处理 oj 需要控制所有路径都有返回值
 return -1;
 }
};

二分查找

通过发现题目发现数据存在二段性，峰值左边数值依次递增，峰值右边依次递减。

算法思路：

峰顶数据特点： arr[i] > arr[i - 1] && arr[i] > arr[i + 1] ；

峰顶左边的数据特点： arr[i] > arr[i - 1] && arr[i] < arr[i + 1] ，也就是呈现上升趋势；

峰顶右边数据的特点： arr[i] < arr[i - 1] && arr[i] > arr[i + 1] ，也就是呈现下降趋势。

因此，根据 mid 位置的信息，可以分为下⾯三种情况：

如果 mid 位置呈现上升趋势，说明我们接下来要在 [mid + 1, right] 区间继续搜索；

如果 mid 位置呈现下降趋势，说明我们接下来要在 [left, mid - 1] 区间搜索；

如果 mid 位置就是⼭峰，直接返回结果。

因为第一个位置和最后一个位置不可能是峰值，所以left=1，right=arr.size()-2;

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

搜索旋转排序数组中的最小值（medium）

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

暴力解法就是遍历数据直接找最小值。当然也可以直接sort排序，直接返回数组首元素（哈哈哈，这个方法抽象）

class Solution {
public:
    int findMin(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[0];
    }
};

二分查找

我们可以发现翻转后的数组来两段区间都是严格递增的。

其中 C 点就是要求的点。

二分的本质：找到一个判断标准，使得查找区间能够一分为二。

通过图像我们可以发现， [A，B] 区间内的点都是严格大于 D 点的值的， C 点的值是严格小

于 D 点的值的。但是当 [C，D] 区间只有一个元素的时候， C 点的值是可能等于 D 点的值

的。因此，初始化左右两个指针 left ， right ：然后根据 mid 的落点，我们可以这样划分下一次查询的区间：

当 mid 在 [A，B] 区间的时候，也就是 mid 位置的值严格大于 D 点的值，下一次查询区间在 [mid + 1，right] 上；

当 mid 在 [C，D] 区间的时候，也就是 mid 位置的值严格⼩于等于 D 点的值，下次

查询区间在 [left，mid] 上。

当区间长度变成 1 的时候，就是我们要找的结果。

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