Tuesday, December 1, 2015

Starting Element of a Rotated Array using Binary Search

Sample Input: 
input={6,7,8,9,0,1,2,3,4,5};
output=4
input={0,1,2,3,4,5,6,7,8,9};
output=0

    public int FindStartIndex(int[] input)    {
        int high = input.length-1;
        int low = 0;
        while(low<high)    {
            if(input[low]<=input[high])
                return low;
            int mid=(high+low)/2;
            if(input[mid]<input[mid+1] && input[mid]<input[mid-1])
                return mid;
            else if(input[mid]>input[low])    {
                //left array is sorted
                //start index is not in left
                low=mid+1;
            }    else if(input[mid]<input[high])    {
                //right array is sorted
                //start index is not in right
                high=mid-1;
            }
        }
        return -1;
    }
UA-39217154-2