【优选算法必刷100题】第023-024题（二分查找）：寻找旋转排序数组中的最小值，点名

前言：

聚焦算法题实战，系统讲解三大核心板块：“精准定位最优解”——优选算法，“简化逻辑表达，系统性探索与剪枝优化”——递归与回溯，“以局部最优换全局高效”——贪心算法，讲解思路与代码实现，帮助大家快速提升代码能力

二分查找专题

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

题目链接：

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

题目描述：

题目示例：

解法（二分查找）：

算法思路：

题目中的数组规则如下图所示：

如图：我们所要求的点是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 的时候，就是我们要找的值

二分查找解法代码（C++）：

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

博主手记（字体还请见谅哈）：

24 .点名

题目链接：

LCR 173. 点名 - 力扣（LeetCode）

题目描述：

题目示例：

解法（二分查找）：

算法思路：

关于这道题中，时间复杂度为 O(N) 的解法有很多种，而且也都比较好想到，这里就不再赘述。本题我们主要介绍的是一个时间复杂度为 O(logn) 的最优解法二分法：

• 在第一个缺失位置的左边，数组内元素都是与数组下标相等的；
• 在第一个缺失位置的右边，数组内的元素都是与数组下标不相等的。

因此，我们可以利用这个 【二段性】 ，来使用 【二分查找】 算法

二分查找解法代码（C++）：

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

博主手记（字体还请见谅哈）：

总结：

往期回顾：【优选算法必刷100题】第021-022题（二分查找）：山峰数组的的峰顶索引、寻找峰值