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.

	#include <iostream>
	#include <vector>
	using namespace std;

	//Actual search method
	int searchRotated(const vector<int> & arr, int s, int low, int high)
	{
	while( low <= high )
	{
	int mid = (low + high)/2;

	if( arr[mid] == s )
	return mid;

	if( arr[low] <= arr[mid]) //left half is sorted
	{
	if( s >= arr[low] && s < arr[mid] )
	high = mid - 1;
	else
	low = mid + 1;
	}
	else
	{
	if( s > arr[mid] && s <= arr[high] )
	low = mid + 1;
	else
	high = mid - 1;
	}
	}
	return -1;// not found
	}
	//wrapper method: searches for 's' in the circularly sorted array arr
	int search(const vector<int> & arr, int s)
	{
	int len = arr.size();
	int low = 0, high = len - 1;
	return searchRotated(arr, s, low, high);
	}


	int main()
	{
	vector<int> input;

	input.push_back(4);
	input.push_back(5);
	input.push_back(6);
	input.push_back(7);
	input.push_back(1);
	input.push_back(2);
	input.push_back(3);

	cout << "3 is found at " << search(input, 3) << endl;
	cout << "6 is found at " << search(input, 6) << endl;
	cout << "8 is found at " << search(input, 8) << endl;
	cout << "2 is found at " << search(input, 2) << endl;
	cout << "1 is found at " << search(input, 1) << endl;
	return 0;
	}

view raw RotateBinarySearch.cpp hosted with

by GitHub

Leave a Reply Cancel reply