LeetCode 33. Search in Rotated Sorted Array

题目描述

You are given an integer array nums sorted in ascending order (with distinct values), and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is guaranteed to be rotated at some pivot.
• -104 <= target <= 104

解题思路

旋转数组的二分查找，这是二分查找的一道变形题。考察点在于二分条件的建立。

对于二分的条件，有两种思路：

1. 始终使用 target 作为二分条件，先和 mid 比较，再和 left 比较，以确定在左半还是右半；
2. 先考虑找出有序的半个数组，然后确定 target 是否在这半个数组中。

两种思路都可以解决，注意：
思路一并不能总是分辨出在哪一半，所以有时候需要两边都查找；
思路二使用 mid 和 left 比较来找出有序半边的时候，注意 left == mid 的特殊情况。

参考代码

/*
 * @lc app=leetcode id=33 lang=cpp
 *
 * [33] Search in Rotated Sorted Array
 */

// @lc code=start
class Solution {
    // All values of nums are unique.
public:
/*
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int l = 0, r = nums.size();
        return bsh(nums, l, r, target);
    }
    int bsh(vector<int>& nums, int l, int r, int target) {
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) {
                if (nums [l] == target) return l;
                if (nums [l] < target) {
                    // r = mid;
                    int res = bsh(nums, l, mid, target);
                    if (res >= 0) return res;
                    return bsh(nums, mid+1, r, target);
                } else { // if (nums [l] > target)
                    l = mid + 1;
                }
            } else { // if (nums[mid] > target)
                if (nums [l] == target) return l;
                if (nums [l] < target) {
                    r = mid;
                } else { // if (nums [l] > target)
                    // l = mid + 1;
                    int res = bsh(nums, l, mid, target);
                    if (res >= 0) return res;
                    return bsh(nums, mid+1, r, target);
                }
            }
        }
        return -1;
    } // AC
*/
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[l] <= nums[mid]) { // left half sorted
                if (nums[l] <= target && target < nums[mid]) r = mid - 1;
                else l = mid + 1;
            } else { // right half sorted
                if (nums[mid] < target && target <= nums[r]) l = mid + 1;
                else r = mid - 1;
            }
        }
        return -1;
    } // attention [3,1], target = 1, you must use nums[l]<=nums[mid]
};
// @lc code=end