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.

LeetCode-Search in Rotated Sorted Array

C++:
class Solution {
public:
    int search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int low=0;
        int high=n-1;
        int mid;
        while(low<=high){
            mid=low+(high-low)/2;
            if(A[mid]==target) return mid;
            else if(A[mid]<target){
                if(A[mid]>=A[low]) low=mid+1;
                else{
                    if(A[high]>=target) low=mid+1;
                    else high=mid-1;
                }
            }else{
                if(A[mid]<=A[high]) high=mid-1;
                else{
                    if(A[low]>target) low=mid+1;
                    else high=mid-1;
                }
            }
        }
        return -1;
    }
};
Java:
public class Solution {
    public int search(int[] A, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int low=0;
        int high=A.length-1;
        int mid;
        while(low<=high){
            mid=low+(high-low)/2;
            if(A[mid]==target) return mid;
            else if(A[mid]>target){
                if(A[mid]<=A[high]) high=mid-1;
                else{
                    if(A[low]>target) low=mid+1;
                    else high=mid-1;
                }
            }else{
                if(A[mid]>=A[low]) low=mid+1;
                else{
                    if(A[high]>=target) low=mid+1;
                    else high=mid-1;
                }
            } 
        }
        return -1;
    }
}