Tuesday, December 1, 2015

Find Index of an element in a Circularly Sorted Array

input=Find 3 in {6,7,8,9,0,1,2,3,4,5};
output=7

    public int FindIndexCircularArray(int element, int[] input)    {
        int high = input.length-1;
        int low = 0;
        while(low<=high)    {
            int mid=(high+low)/2;
            if(element==input[mid])
                return mid;
            else if(input[low]<=input[mid])    {
                //left array is sorted
                if(element>=input[low] && element<input[mid])
                    high=mid-1;
                else    low=mid+1;
            }    else if(input[mid]<=input[high])    {
                //right array is sorted
                if(element>input[mid] && element<=input[high])
                    low=mid+1;
                else    high=mid-1;
            }
        }
        return -1;
    }

UA-39217154-2