1 class Solution { 2 public: 3     int binarySearch(int A[], int low, int high, int target) 4     { 5         int mid = (high+low)/2; 6          7         if(low <= high) 8         { 9             if(target == A[mid]) 10                 return mid;11             else if(target > A[mid])12                 return binarySearch(A, mid+1, high, target);13             else14                 return binarySearch(A, low, mid-1, target);15         }16         return -1;17     }18     19     int search(int A[], int n, int target) 20     {21         return search(A, 0, n-1, target);22     }23     24     int search(int A[], int low, int high, int target) 25     {26         27         int mid =  (high+low)/2;28         29         if(low > high)30             return -1;31         32         if(A[mid] == target)33             return mid;34         35         if(A[mid] >= A[low]) // the pivot is in the bottom half36         {37             if(target >= A[low] && target < A[mid]) // target in the first half38             {39                 return binarySearch(A, low, mid-1, target);40             }41             else // target in the bottom half42             {43                 return search(A, mid+1, high, target);44             }45         }46         else // the pivot is in the first half47         {48             if(target >= A[mid+1] && target <= A[high]) // target in the bottom half49             {50                 return binarySearch(A, mid+1, high, target);51             }52             else // target in the first half53             {54                 return search(A, low, mid-1, target);55             }            56         }57     }58 };

 1 class Solution { 2     public: 3         int search(int A[], int n, int target) { 4             int first = 0, last = n; 5             while (first != last) { 6                 const int mid = (first + last) / 2; 7                 if (A[mid] == target) 8                     return mid; 9                 if (A[first] <= A[mid]) { // the pivot is in the bottom half10                     if (A[first] <= target && target < A[mid]) //target in the first half11                         last = mid;12                     else13                         first = mid + 1; //target in the bottom half14                 } else {// the pivot is in the first half15                     if (A[mid] < target && target <= A[last-1])//target in the bottom half16                         first = mid + 1;17                     else18                         last = mid;//target in the first half19                 }20             }21             return -1;22         }23 };