【题目】

 

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.

【二分思路】

分情况讨论，数组可能有以下三种情况：

然后，再看每一种情况中，target在左边还是在右边，其中第一种情况还可以直接判断target有可能不在数组范围内。

1 public class Solution { 2     public int search(int[] A, int target) { 3         int len = A.length; 4         if (len == 0) return -1; 5         return binarySearch(A, 0, len-1, target); 6     } 7      8     public int binarySearch(int[] A, int left, int right, int target) { 9         if (left > right) return -1;10         11         int mid = (left + right) / 2;12         if (A[left] == target) return left;13         if (A[mid] == target) return mid;14         if (A[right] == target) return right;15         16         //图示情况一17         if (A[left] < A[right]) { 18             if (target < A[left] || target > A[right]) {    //target不在数组范围内19                 return -1;20             } else if (target < A[mid]) {                   //target在左边21                 return binarySearch(A, left+1, mid-1, target);22             } else {                                        //target在右边23                 return binarySearch(A, mid+1, right-1, target);24             }25         } 26         //图示情况二27         else if (A[left] < A[mid]) { 28             if (target > A[left] && target < A[mid]) {      //target在左边29                 return binarySearch(A, left+1, mid-1, target);30             } else {                                        //target在右边31                 return binarySearch(A, mid+1, right-1, target);32             }33         } 34         //图示情况三35         else { 36             if (target > A[mid] && target < A[right]) {     //target在右边37                 return binarySearch(A, mid+1, right-1, target);38             } else{                                         //target在左边39                 return binarySearch(A, left+1, mid-1, target);40             }41         }42     }43 }

 

我的解法，不是最优解

1 class Solution { 2 public: 3     int search(int A[], int n, int target) { 4         if(A==NULL||n<1) return -1; 5         int index=0; 6         for(int i=1;i
     
      A[i]){ 8                 index=i; 9                 break;10             }11         }12         int left,right;13         if(target>=A[0]&&target<=A[index-1]){14             left=0;15             right=index-1;16         }else if(target>=A[index]&&target<=A[n-1]){17             left=index;18             right=n-1;19         }else20             return -1;21         while(left<=right){22             int mid=(left+right)/2;23             if(target==A[left])24                 return left;25             if(target==A[right])26                 return right;27             if(target==A[mid])28                 return mid;29             if(target>A[left]&&target