【十五】【算法分析与设计】二分查询（3）

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]

• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

• n == nums.length

• 1 <= n <= 5000

• -5000 <= nums[i] <= 5000

• nums 中的所有整数 互不相同

• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

我们可以将nums数组分成两个部分[0,x][x+1,n-1]，[0,x]部分全部都大于等于nums[0]，[x+1,n-1]全部都小于nums[0]。

处理边界情况，就是如果一直都是递增，即nums[n-1]>nums[0] 此时最小值为nums[0]。否则一定发生了一定有效的旋转。

因因此我们希望left和right在x+1这个位置相遇，可以定义[0,left-1]全都是大于等于nums[0]的数，[right,n-1]全都是小于nums[0]的数。也就是[left,right]区间内，一直存在我们需要找的数。直到区间的长度大小为1。

因为right=mid，所以mid不可以+1操作。

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

        return nums[left];
    }
};

int n = nums.size();

获取数组 nums 的长度。

if (nums[n - 1] > nums[0])return nums[0];

如果数组的最后一个元素大于第一个元素，说明数组是完全有序的（没有旋转），直接返回第一个元素作为最小值。

int left = 0, right = n - 1;

初始化两个指针 left 和 right，分别指向数组的起始索引和结束索引。

二分查找

while (left < right) {

使用二分查找，当 left 小于 right 时，执行循环。

int mid = left + (right - left) / 2;

计算中间索引 mid。

if (nums[mid] >= nums[0]) left = mid + 1;

如果 mid 处的值大于等于数组的第一个元素，说明最小元素在 mid 的右侧。

else right = mid;

如果 mid 处的值小于数组的第一个元素，说明最小元素在 mid 或其左侧。

return nums[left];}

循环结束时，left 和 right 指向相同的位置，该位置就是最小元素的索引，返回该位置上的元素作为数组的最小值。

时间复杂度和空间复杂度分析

时间复杂度：O(log n)，其中 n 是数组 nums 的长度。二分查找的时间复杂度为对数级别。

空间复杂度：O(1)，代码中没有使用额外的存储空间，只使用了有限的几个变量。

LCR 173. 点名

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

示例 1:

输入: records = [0,1,2,3,5] 输出: 4

示例 2:

输入: records = [0, 1, 2, 3, 4, 5, 6, 8] 输出: 7

提示：

1 <= records.length <= 10000

我们依旧可以将records分成两部分，[0,x][x+1,n-1]，[0,x]部分的元素值与下标值相等，[x+1,n-1]的元素值与下标值不相等。我们希望left和right在x+1这个位置相遇，因此可以定义[0,left-1]全都是元素值与下标值相等的数，[right,n-1]全都是元素值与下标值不相等的数。

right=mid，所以mid不可以进行+1操作。

处理边界情况，考虑首尾数据丢失的情况。

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

int n = records.size();

获取数组 records 的长度。

if (records[n - 1] == n - 1)return n;

如果数组的最后一个元素的值等于它的索引（假设索引从 0 开始），则返回 n。这可能表示所有记录都是连续的，并且没有缺失。

if (records[0] != 0)return 0;

如果数组的第一个元素的值不等于 0，返回 0。这可能表示第一个记录丢失。

int left = 0, right = n - 1;

初始化两个指针 left 和 right，分别指向数组的起始索引和结束索引。

二分查找

while (left < right) {

使用二分查找，当 left 小于 right 时，执行循环。

int mid = left + (right - left) / 2;

计算中间索引 mid。

if (records[mid] == mid) {

如果 mid 处的值等于它的索引，说明到目前为止记录是连续的。

left = mid + 1;

将 left 指针移动到 mid + 1。

} else right = mid;

如果 mid 处的值不等于它的索引，说明缺失的记录在 mid 或其左侧。

return left;}

最后，当 left 和 right 重合时，返回 left 作为缺失记录的值。

时间复杂度和空间复杂度分析

时间复杂度：O(log n)，其中 n 是数组 records 的长度。二分查找的时间复杂度为对数级别。

空间复杂度：O(1)，代码中没有使用额外的存储空间，只使用了有限的几个变量。

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！