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.

**Thoughts:**

This is a modified version of binary search. Each time we half the array, and determine which part is sorted (there must be at least one of them). We then check if the target falls in the sorted part, we then apply the original version of binary search to it. Otherwise we recursively or iteratively go to the other half.

**Code (Java):**

public class Solution { public int search(int[] A, int target) { int low = 0; int high = A.length - 1; while(low <= high) { int mid = low + (high - low) / 2; if(target == A[mid]) return mid; if(A[low] <= A[mid]) { // left part sorted if(A[low] <= target && target < A[mid]) high = mid - 1; else low = mid + 1; } else { // right part sorted if(A[mid] < target && target <= A[high]) low = mid + 1; else high = mid - 1; } } return -1; } }

**Code (C++):**

class Solution { public: int search(int A[], int n, int target) { int low = 0; int high = n - 1; while(low <= high) { int mid = low + (high - low) / 2; if(A[mid] == target) return mid; if(A[low] <= A[mid]) { // left part sorted if(A[low] <= target && target < A[mid]) high = mid - 1; else low = mid + 1; } else { if(A[mid] < target && target <= A[high]) low = mid + 1; else high = mid - 1; } } return -1; } };