Given a target integer T and an integer array A, A is sorted in ascending order first, then shifted by an arbitrary number of positions.

For Example, A = {3, 4, 5, 1, 2} (shifted left by 2 positions). Find the index i such that A[i] == T or return -1 if there is no such index.

Assumptions

• There are no duplicate elements in the array.

Examples

• A = {3, 4, 5, 1, 2}, T = 4, return 1
• A = {1, 2, 3, 4, 5}, T = 4, return 3
• A = {3, 5, 6, 1, 2}, T = 4, return -1

Corner Cases

• What if A is null or A is of zero length? We should return -1 in this case.

Solution: 先A[mid]与A[end]比较：1.若A[mid]<A[end]: a.A[mid]<=target<=A[end]，则start = mid, b.否则end = mid; 2.若A[mid]>A[end]: a.A[start]<=target<=A[mid]，则end = mid, b.否则start = mid

有duplicate时，直接loop through就好，因为[1,1,1,1,1…] O(n)

  public int search(int[] array, int target) {
    if (array == null || array.length == 0) {
      return -1;
    }
    int start = 0, end = array.length - 1;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (array[mid] < array[end]) {
        if (array[mid] <= target && target <= array[end]) {
          start = mid;
        } else {
          end = mid;
        } 
      } else {
        if (array[start] <= target && target <= array[mid]) {
          end = mid;
        } else {
          start = mid;
        } 
      }
    }
    if (array[start] == target) {
      return start;
    } else if (array[end] == target) {
      return end;
    }
    return -1;
  }