Search in Rotated Sorted Array 系列

相关题目:

主要考察对 Binary Search 的理解。

Find Minimum in Rotated Sorted Array 让找一个 offset,实现还是蛮简单的,只需要注意完全没有 rotate 的 corner case 即可。实现如下:

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

Search in Rotated Sorted Array 也较为简单,思路如下:

  1. 找到 offet,把问题简化成普通 Binary Search 问题。
  2. 无脑 Binary Search。

实现如下。

class Solution {  
 public:
  int GetOffset(vector<int> &nums) {
    int lo = 0;
    int hi = nums.size() - 1;

    while (lo < hi) {
      if (nums[lo] < nums[hi]) {
        return lo;
      }
      int mid = lo + (hi - lo) / 2;
      if (nums[mid] < nums[lo]) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    return lo;
  }

  int BinarySearchWithOffset(vector<int> &nums,
                             int offset,
                             int target) {
    const int n = nums.size();
    int lo = 0;
    int hi = n - 1;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      if (nums[(mid + offset) % n] >= target) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    int index = (lo + offset) % n;
    return nums[index] == target ? index : -1;
  }

  int search(vector<int> &nums, int target) {
    int offset = GetOffset(nums);
    return BinarySearchWithOffset(nums, offset, target);
  }
};

前面的两题都保证了 no duplicate,而 Search in Rotated Sorted Array II 让你思考存在 duplicate 的情况。

考虑一个 sorted array ...xxxxxxxx...x 为相同的数),将其 rotate 成 xxxx..[a]...xxxx。如果 a = x,那么这个时候是没有办法判段下一步应该搜索左边还是右边的。所以,对于存在 duplicate 的情况,worst case complexity 是 $O(n)$。