Search key in a rotated sorted array without repetition of elements Is there any improvement possible in this implementation?

#include&lt;iostream&gt;

int search( int array[], int N, int key )
{
    int first_index = 0;
    int last_index = N - 1;

    while ( last_index &gt;= first_index )
    {
        int middle_index = last_index + first_index / 2;

        if( array[ middle_index ] == key )
           return middle_index;

        if ( array[ first_index ] &lt; array [ middle_index ] )
        {
            if( key &gt;=  array[ first_index ] &amp;&amp; key &lt; array [ middle_index ] )
                last_index = middle_index - 1;
            else
                first_index = middle_index + 1;                
        }
        else
        { 
            if( key &gt; array [ middle_index ] &amp;&amp; key &lt;= array [ last_index ])
                first_index = middle_index + 1;
            else
                last_index = middle_index - 1;
        }         
    }
    return -1;    
}

int main()
{
    int array[] = { 2, 4, 5, 6, 7, 0, 1 };
    int index = search( array, 7, 0 );

    std::cout&lt;&lt;"index :"&lt;&lt;index;

}
Generally speaking, well-designed algorithms in C++ work with iterators, not with arrays and size or with full collections. By using iterators, you can make your algorithm work with any standard collection. Since you heavily rely on the indices and make math with them, I guess that you algorithm is only meant to work with random-access iterators, but we can still generalize it with iterators to make it work with arrays, std::array, std::vector and std::deque with trivial changes.

Make it work with any random-access iterator


First, let's change the signature:

template&lt;typename RandomAccessIt&gt;
int search(RandomAccessIt begin, RandomAccessIt end, int key);

We don't have the size N anymore, but we can still compute last_index with the iterators:

int last_index = std::distance(begin, end) - 1;

Now, all you have to do is replace array by begin everywhere and change your main:

int main()
{
    int array[] = { 2, 4, 5, 6, 7, 0, 1 };
    int index = search(std::begin(array), std::end(array), 0);

    std::cout&lt;&lt;"index :"&lt;&lt;index;
}



Return the iterator, not the offset

Searching algorithms in the standard library tend to return the iterator where the value was found - if it was found -, and the end iterator otherwise. Once again, you can implement that with only a few changes:


Change the return type to RandomAccessIt:

template&lt;typename RandomAccessIt&gt;
RandomAccessIt search(RandomAccessIt begin, RandomAccessIt end, int key);

Instead of returning middle_index, return the corresponding iterator:

return std::next(begin, middle_index);

Instead of returning -1 when the value has not been found, return the end iterator:

// The key was not found
return end;



Make it fully iterator-based

By using the functions in &lt;iterator&gt;, you can make your algorithm have a more "iterator-oriented" feel. I almost converted it to work with bidirectional iterators (with the additional cost than std::distance is \$O(n)\$ instead of \$O(1)\$ for bidirectional iterators) but stopped myself since I would have to alter a bit the logic of your algorithm and comparing the original and the new versions would have been trickier. Let's say that the final steps are left as an exercise to the reader :p

template&lt;typename RandomAccessIt&gt;
RandomAccessIt search(RandomAccessIt begin, RandomAccessIt end, int key)
{
    RandomAccessIt last = std::prev(end);

    while ( last &gt;= begin )
    {
        RandomAccessIt middle = std::next(begin, std::distance(begin, last) / 2);

        if( *middle == key )
           // The key was found
           return middle;

        if ( *begin &lt; *middle )
        {
            if( key &gt;= *begin &amp;&amp; key &lt; *middle )
                last = std::prev(middle);
            else
                begin = std::next(middle);                
        }
        else
        { 
            if( key &gt; *middle &amp;&amp; key &lt;= *last )
                begin = std::next(middle);
            else
                last = std::prev(middle);
        }         
    }
    // The key was not found
    return end;    
}


Make it work for any comparable type

Turning this index-based algorithm to an iterator-based algorithm made me realize that there weren't any tricky things making use of the value of key to be more efficient and that the key was only used for comparison. Therefore, you can also make the searched type generic instead of restricting it to int. Actually, it is as simple as merely changing its signature and it works with any LessThanComparable type:

template&lt;typename RandomAccessIt, typename LessThanComparable&gt;
RandomAccessIt search(RandomAccessIt begin, RandomAccessIt end, LessThanComparable key);