Finding an element in a circularly sorted array

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

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.