Search in a Circular Sorted Array

Given a circular sorted array say A = { 2,3,4,5,6,7,8,9,0,1 }, find a number in it.

If the array is not circular, we can use binary search to find the key. But if the array is circular we don't know where is the starting point (pivot element). Obviously we can do a linear search to find the element. But if the input array is very large the worst case performance will be very bad. We can take advantage of the fact that the array is sort and use binary search algorithm to find the element in O(N log N).

Approach:

Find the middle value of the input array a.

If a[0] < a[mid], then all values in the first half of the array are sorted.

If a[mid] < a[last], then all values in the second half of the array are sorted.

Take the sorted half, and check whether your value lies within it (key lies between the sorted half).

• If so, binary search that half.
• If it doesn't, it must be in the unsorted half. Take that half and repeat this process

 
#include <iostream>
#include <vector>
#include <assert.h>

template<typename T, typename type>
int binary_search(const T& a, int left, 
                  int right, type key) {

    while (left <= right) {
        int mid = (right-left)/2 + left;

        // base case 1
        if (a[mid] == key)
            return mid;

        // mid less than key. Move to right
        if (a[mid] < key) {
            left = mid+1;
        }
        else {
            right = mid-1;
        }
    }

    return -1;
}

template<typename T, typename type>
int circular_search(const T& a, int left, 
                    int right, type key) {

    // base case 1
    int mid = (right-left)/2 + left;
    if (a[mid] == key)
        return mid;

    // left array is sorted.
    if (a[0] < a[mid]) {

        if (key > a[left] && key < a[mid]) {
            return binary_search(a, left, mid-1, key);
        }
        else {
            return circular_search(a, mid+1, right, key);
        }
    }
    // right array is sorted
    else if (a[mid] < a[right]) {
        if (key > a[mid] && key < a[right])
            return binary_search(a, mid+1, right, key);
        else
            return circular_search(a, left, mid-1, key);

    }

    return -1;

}

template<typename T>
void print(const T&a) {
    typedef typename T::const_iterator iterator;
    iterator start = a.begin();
    iterator end = a.end();
    for(; start!=end; ++start)
        std::cout << *start << " ";
    std::cout << std::endl;
}

int main() {
    typedef std::vector<int> Input;
    Input temp;
    int n =0;
    
    // get n from user
    std::cin >> n;

    for(int i=0; i<n; ++i) {
        temp.push_back(i*2);
    }
    Input data;
    data.resize(temp.size());

    // Rotate the input sequence
    std::rotate_copy(temp.begin(), temp.begin()+4, 
                     data1.end(), data.begin());
    print(data);

    // get key from user
    int key=0;
    std::cin >> key;

    int found = circular_search<Input, int>(data, 0, n-1, key);
    if (found)
    {
        assert(key == data[found]);
        std::cout << data[found] 
                  << " found @ pos " 
                  << found << std::endl;
    }
    else
        std::cout << key 
                  << " not found" 
                  << std::endl;

    return 0;

}