Search in Rotated Sorted Array

    (i.e., 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.

    Example

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

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

    Challenge

    题解 - 找到有序数组

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

    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) {
    9.         int lb = 0, ub = A.length - 1;
    10.         while (lb + 1 < ub) {
    11.             int mid = lb + (ub - lb) / 2;
    12.             if (A[mid] == target) return mid;
    14.             if (A[mid] > A[lb]) {
    15.                 // case1: numbers between lb and mid are sorted
    16.                 if (A[lb] <= target && target <= A[mid]) {
    17.                     ub = mid;
    18.                 } else {
    19.                     lb = mid;
    20.                 }
    21.             } else {
    22.                 // case2: numbers between mid and ub are sorted
    23.                 if (A[mid] <= target && target <= A[ub]) {
    24.                     lb = mid;
    25.                 } else {
    26.                 }
    27.             }
    28.         }
    30.         if (A[lb] == target) {
    31.             return lb;
    32.         } else if (A[ub] == target) {
    33.             return ub;
    34.         }
    35.         return -1;
    36.     }
    37. }
    1. 若target == A[mid]，索引找到，直接返回
    2. 寻找局部有序数组，分析A[mid]和两段有序的数组特点，由于旋转后前面有序数组最小值都比后面有序数组最大值大。故若A[start] < A[mid]成立，则start与mid间的元素必有序（要么是前一段有序数组，要么是后一段有序数组，还有可能是未旋转数组）。
    3. 接着在有序数组A[start]~A[mid]间进行二分搜索，但能在A[start]~A[mid]间搜索的前提是。
    4. 接着在有序数组A[mid]~A[end]间进行二分搜索，注意前提条件。
    5. 搜索完毕时索引若不是mid或者未满足while循环条件，则测试A[start]或者A[end]是否满足条件。
    6. 最后若未找到满足条件的索引，则返回-1.

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