33. Search in Rotated Sorted Array

发表于 | 分类于 | 浏览 次

Suppose an array sorted in ascending order 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]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

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

Example 2:

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

比较朴素的做法是先按照剑指offer上的做法找出整个数组中的最小值，然后通过最小值将整个数组分为两个有序子数组。然后分别根据target的值在第一个或者第二个子数组中使用二分查找。

更好的做法是直接使用二分查找。

解法1：二分查找

假设当前要查找的区间是[lo, hi]，mid = (lo + hi) / 2。

  • 当nums[mid] >= nums[lo]时，区间[lo，mid]内不包含旋转。当[lo，mid]内不包含旋转，那么这个区间是一个递增序列。
    • 那么如果target >= nums[lo]，说明target如果存在，则应该存在于这个区间内。令hi = mid；
    • 如果target > nums[mid]，说明target如果存在，只能存在于右边，则令lo = mid + 1；
    • 如果target < nums[lo]，因为nums[lo]是整个区间中的最小值，那么说明target如果存在，只能存在于旋转位置之后的第二个递增子数组中。令lo = mid + 1。
  • 当nums[mid] < nums[lo]时，区间[lo，mid]内包含旋转。
    • 当target >= nums[lo]时，说明target如果存在，那么应该存在于lo之后，最小值所在位置之前。令hi = mid。
    • 当target <= nums[mid]时，说明target如果存在，那么应该存在于最小值位置到mid之间。令hi = mid。
    • 如果target > nums[mid] && nums[lo] > target时，说明target如果存在，只能存在与第二个递增子数组中mid后面的位置，所以令lo = mid + 1。

所以，在三种情况下到右半区间中去寻找，而其他情况下到左半边寻找。
向右半区间寻找的这两种情况是：

  • target > nums[mid] >= nums[lo]
  • nums[mid] >= nums[lo] > target
  • target >= nums[lo] > nums[mid]

在另外三种情况中应该向左半边寻找：

  1. nums[lo] <= target <= nums[mid]
  2. target <= nums[mid] < nums[lo]
  3. nums[mid] < nums[lo] <= target

第一项中nums[lo] <= nums[mid]，第二项中nums[lo] > nums[mid]，同样第三项中nums[lo] > nums[mid]
第二项中target < nums[lo]，第一项中target >= nums[lo]，第三项中target >= nums[lo]
第三项中nums[mid] < target，第一项中nums[mid] >= nums[lo]，第二项中nums[mid] >= nums[lo]

从以上分析可知，这三个条件最多满足一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size()  - 1;
        while(lo < hi){
            int mid = (lo + hi) / 2;
            if((nums[lo] <= nums[mid]) ^ (target < nums[lo]) ^ (nums[mid] <  target)){
               hi = mid;
            }else{
                lo = mid + 1;
            }
        }
        return lo == hi && nums[lo] == target ? lo : -1;
    }
};

此外，当退出循环之外，会出现哪些情况？
必须判断lo是否等于hi的情况：

1
2
Input: nums = [], target = 5
Output: -1

在这个测试用例下，lo初值为0，hi初值为-1，初值不等，但是不会进入while循环。

1
2
Input: nums = [3], target = 5
Output: -1

在这个测试用例中，同样不会进入到循环中，因为进入循环的条件为lo < hi，而这里lo和hi的初值都为0。

一旦进入while循环，唯一退出循环的条件就是lo == hi。因为lo<=mid <= hi，所以，经过一轮循环之后，lo和hi的值有几种情况：

  • 循环之前，因为lo < hi，所以，lo和hi差值最小时，lo = x，hi = x + 1，mid = x，

    • 条件表达式的结果：
      因为条件表达式nums[lo] <= nums[mid]) ^ (target < nums[lo]) ^ (nums[mid] < target)的结果在lo = mid = hi时，必然为0。这是因为nums[lo] == nums[mid]，nums[lo] <= nums[mid]必然成立。
      • 当target < nums[lo]和nums[mid] < target中有一个成立时，(target < nums[lo]) ^ (nums[mid] < target)的结果为1。那么最后的结果为0。此时执行的表达式是lo = mid + 1。
      • 当target == nums[lo]时，target < nums[lo]和nums[mid] < target中都不成立时，(target < nums[lo]) ^ (nums[mid] < target)的结果为0。那么最后的结果为1，执行的表达式是hi = mid。
    • 循环中执行的表达式是hi = mid时，则循环之后，lo = x，hi = x。
    • 循环中执行的表达式是lo = mid + 1时，则循环之后，lo = x + 1，hi = x + 1。

    所以，在循环之后，lo和hi可能会因为相等而不满足while循环的条件而退出。