二分查找：旋转

0033. 搜索旋转排序数组 (opens new window)

题目

整数数组 nums 按升序排列，数组中的值 互不相同 。

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1 。

解析

对于旋转数组，我们无法直接根据 nums[mid] 与 target 的大小关系来判断 target 是在 mid 的左边还是右边，因此需要「分段讨论」。

1. 通过二分找到数组旋转点；
2. 确定 target 在哪个区间；
3. 子区间内二分查找。

二分算法，见 算法模板：整数二分。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;

        // 找到数组旋转点（左侧最后一个下标）
        // 左侧：nums[i] >= nums[0]
        // 右侧：nums[i] < nums[0]
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2 + 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        // 确定 target 在哪个区间，设置 l、r
        if (target >= nums[0]) l = 0;
        else l = r + 1, r = nums.size() - 1;

        // 子区间内二分查找（第一个 >= target 的元素下标）
        // 左侧：nums[i] < target
        // 右侧：nums[i] >= target
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        // 注意：此时 l 可能越界，返回时用 r 判断
        return nums[r] == target ? r : -1;
    }
};

0081. 搜索旋转排序数组 II (opens new window)

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

解析

这是 0033. 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。

只需在搜索前做一下预处理，把最右侧与数组第一个数字相同的数字删去，避免 $nums[l] = nums[mid] = nums[r]$，从而正常进行二分找到旋转点。

代码

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;

        // 预处理，把右侧重复数字删去
        while (l < r && nums[l] == nums[r]) r--;
        
        // 二分找到数组旋转点
        while (l < r) {
            int mid = l + (r - l) / 2 + 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        // 确定 target 在哪个区间，重新设置左右指针
        if (target >= nums[0]) l = 0;
        else l = r + 1, r = nums.size() - 1;

        // 在子区间内二分查找
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        // 注意：此时 l 可能越界，返回时用 r 判断
        return nums[r] == target;
    }
};

0153. 寻找旋转排序数组中的最小值 (opens new window)

题目

已知一个长度为 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，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

解析

旋转后的数组可看做两个升序数组的拼接，且后一个数组的值比前一个数组的所有值都小。

• 若 nums[mid] < nums[right]，说明此时 mid 位于后一个数组中，舍弃 mid 右侧的元素；
• 若 nums[mid] > nums[right]，说明此时 mid 位于前一个数组中，舍弃 mid 左侧的元素。

代码

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

0154. 寻找旋转排序数组中的最小值 II (opens new window)

题目

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

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
• 若旋转 7 次，则可以得到 [0,1,4,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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

解析

这是 0153. 寻找旋转排序数组中的最小值 的延伸题目，本题中的 nums 可能包含重复元素。

只需额外考虑一种特殊情况，当 $nums[left] = nums[mid] = nums[right]$ 时，此时一定可以排除右侧端点，缩小右侧区间即可。

代码

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