【优选算法】Binary-Blade：二分查找的算法刃（下）

DARLING Zero two

发布于 2025-01-08 08:58:08

3600

代码可运行

文章被收录于专栏：C语言C语言

运行总次数：0

代码可运行

本篇接上一篇二分查找，主要通过部分题目熟悉二分查找的进阶使用，重点强调二段性，找到两个区间不同的地方在哪，多画图划分界限

1.山脉数组的峰顶索引

✏️题目描述：

✏️示例：

传送门：山脉数组的峰顶索引

题解: 💻第一步：

首先确定二段性，把顶峰放到左区间还是右区间取决于你自己，会根据取法不同而导致代码不同，但是都能求出顶峰索引，这里我们放到左区间

💻第二步：

按照我们的划分方式，要确保左边区间不会越过分界，右边区间同理，就要用mid和mid-1这种划分方式。如果在左区间，那么mid会有等于峰顶索引，即left = mid；如果在右区间，mid及其后面的值都不可能是峰顶索引，即right = mid - 1

💻细节问题:

对于二分查找进阶模版，如果在if语句的函数体里有减法操作时，那么计算mid的公式就要+1

💻代码实现:

#include <iostream>
#include <vector>
using namespace std;

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

2.寻找峰值

✏️题目描述：

✏️示例：

传送门：寻找峰值

题解: 💻第一步：

首先确定二段性，可以分为在上坡或者下坡，其实这道题和山脉数组的峰顶索引是一样的，这里我们顶峰放在右区间里

💻第二步：

按照我们的划分方式，要确保右边区间不会越过分界，左边区间同理，就要用mid和mid+1这种划分方式。如果在右区间，那么mid会有等于峰顶索引，即right = mid；如果在左区间，mid及其前面的值都不可能是峰顶索引，即left = mid + 1

💻代码实现:

#include <iostream>
#include <vector>
using namespace std;

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])
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }
        return left;
    }
};

3.寻找旋转排序数组中的最小值

✏️题目描述：

✏️示例：

传送门：寻找旋转排序数组中的最小值

题解: 💻第一步：

根据画图，似乎不太好确认二段性，但我们可以发现以D点为分界点，左区间的数（A到B）都大于D，右区间的数（C到D）都小于D，那么由此就能确定二段性，不断向中寻找最小的数

💻第二步：

如果在右区间，那么mid会有等于最小值，即right = mid；如果在左区间，mid及其前面的值都不可能是最小值，即left = mid + 1

💻代码实现:

#include <iostream>
#include <vector>
using namespace std;

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

4.点名

✏️题目描述：

✏️示例：

传送门：点名

题解: 💻第一步：

在连续数组的前提下，缺失数字的位置开始下标与实际值不同，很明显二段性立马就出来了

💻第二步：

如果在右区间，那么mid会有等于缺失值的实际位置索引，即right = mid；如果在左区间，mid及其前面的值都不可能是缺失值的实际位置索引，即left = mid + 1

💻代码实现:

#include <iostream>
#include <vector>
using namespace std;

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