Search in Rotated Sorted Array

Question

Problem Statement

Suppose a sorted array 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.

Example

For [4, 5, 1, 2, 3] and target=1, return 2.

For [4, 5, 1, 2, 3] and target=0, return -1.

Challenge

O(logN) time

题解 - 找到有序数组

对于旋转数组的分析可使用画图的方法，如下图所示，升序数组经旋转后可能为如下两种形式。

Rotated Array

对于有序数组，使用二分搜索比较方便。分析题中的数组特点，旋转后初看是乱序数组，但仔细一看其实里面是存在两段有序数组的。刚开始做这道题时可能会去比较target和A[mid], 但分析起来异常复杂。该题较为巧妙的地方在于如何找出旋转数组中的局部有序数组，并使用二分搜索解之。结合实际数组在纸上分析较为方便。

C++

  1. /**
  2.  * 本代码fork自
  3.  * http://www.jiuzhang.com/solutions/search-in-rotated-sorted-array/
  4.  */
  5. class Solution {
  6.     /**
  7.      * param A : an integer ratated sorted array
  8.      * param target :  an integer to be searched
  9.      * return : an integer
  10.      */
  11. public:
  12.     int search(vector<int> &A, int target) {
  13.         if (A.empty()) {
  14.             return -1;
  15.         }
  17.         vector<int>::size_type start = 0;
  18.         vector<int>::size_type end = A.size() - 1;
  19.         vector<int>::size_type mid;
  21.         while (start + 1 < end) {
  22.             mid = start + (end - start) / 2;
  23.             if (target == A[mid]) {
  24.                 return mid;
  25.             }
  26.             if (A[start] < A[mid]) {
  27.                 // situation 1, numbers between start and mid are sorted
  28.                 if (A[start] <= target && target < A[mid]) {
  29.                     end = mid;
  30.                 } else {
  31.                     start = mid;
  32.                 }
  33.             } else {
  34.                 // situation 2, numbers between mid and end are sorted
  35.                 if (A[mid] < target && target <= A[end]) {
  36.                     start = mid;
  37.                 } else {
  38.                     end = mid;
  39.                 }
  40.             }
  41.         }
  43.         if (A[start] == target) {
  44.             return start;
  45.         }
  46.         if (A[end] == target) {
  47.             return end;
  48.         }
  49.         return -1;
  50.     }
  51. };

Java

  1. public class Solution {
  2.     /**
  3.      *@param A : an integer rotated sorted array
  4.      *@param target :  an integer to be searched
  5.      *return : an integer
  6.      */
  7.     public int search(int[] A, int target) {
  8.         if (A == null || A.length == 0) return -1;
  10.         int lb = 0, ub = A.length - 1;
  11.         while (lb + 1 < ub) {
  12.             int mid = lb + (ub - lb) / 2;
  13.             if (A[mid] == target) return mid;
  15.             if (A[mid] > A[lb]) {
  16.                 // case1: numbers between lb and mid are sorted
  17.                 if (A[lb] <= target && target <= A[mid]) {
  18.                     ub = mid;
  19.                 } else {
  20.                     lb = mid;
  21.                 }
  22.             } else {
  23.                 // case2: numbers between mid and ub are sorted
  24.                 if (A[mid] <= target && target <= A[ub]) {
  25.                     lb = mid;
  26.                 } else {
  27.                     ub = mid;
  28.                 }
  29.             }
  30.         }
  32.         if (A[lb] == target) {
  33.             return lb;
  34.         } else if (A[ub] == target) {
  35.             return ub;
  36.         }
  37.         return -1;
  38.     }
  39. }

源码分析

  1. 若target == A[mid]，索引找到，直接返回
  2. 寻找局部有序数组，分析A[mid]和两段有序的数组特点，由于旋转后前面有序数组最小值都比后面有序数组最大值大。故若A[start] < A[mid]成立，则start与mid间的元素必有序（要么是前一段有序数组，要么是后一段有序数组，还有可能是未旋转数组）。
  3. 接着在有序数组A[start]~A[mid]间进行二分搜索，但能在A[start]~A[mid]间搜索的前提是A[start] <= target <= A[mid]。
  4. 接着在有序数组A[mid]~A[end]间进行二分搜索，注意前提条件。
  5. 搜索完毕时索引若不是mid或者未满足while循环条件，则测试A[start]或者A[end]是否满足条件。
  6. 最后若未找到满足条件的索引，则返回-1.

复杂度分析

分两段二分，时间复杂度仍近似为 O(\log n).