Monday, March 17, 2014

Finding an element in a circularly sorted array

Given a circularly sorted array, how to search for an element efficiently?

For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3.

Since the array is sorted but rotated, we can expect it to be solved using the binary search technique.

We can design an algorithm like this. We first check if the middle element equals the target element. If so, we return the mid.

Otherwise we check to see if the left half is sorted or right half is sorted. In any case only one portion will be sorted. We have to narrow down our search based on the range of elements which the target belongs to .

           if( arr[low] <= arr[mid]) //left half is sorted
        {
            //If target lies in first half

            if( s >= arr[low] && s < arr[mid] )
                high = mid - 1;
            else
                low = mid + 1; // narrow down to right half
        }
        else // Right half is sorted
        {
            if( s > arr[mid] && s <= arr[high] )
                low = mid + 1;
            else
                high = mid - 1;
        }


Here is the iterative implementation of the above algorithm. This algorithm runs in O( log n ) time complexity.