算法魅力-二分查找实战

目录

前言

算法定义

朴素二分模版

二分查找 

 二分的边界查找

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

 暴力算法

二分查找 

边界查找分析

 山峰数组的峰顶

暴力枚举

二分查找

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

二分查找

结束语

前言

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

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

算法定义

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

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

左边界查找

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

 综上所述：

 山峰数组的峰顶

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

二分查找

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

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

结束语

二分查找的讲解就到此结束啦，各位，相信通过这些题目的讲解大家对二分有了全新的认识和理解，下个算法我们将学习前缀和，欢迎大家来指导交流。

最后感谢各位友友的支持！！！