patterncppMinor

Search key in a rotated sorted array without repetition of elements

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

withoutsearchelementsrotatedarrayrepetitionsortedkey

Problem

Is there any improvement possible in this implementation?

#include

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

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

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

        if ( array[ first_index ] =  array[ first_index ] && key  array [ middle_index ] && key <= 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<<"index :"<<index;

}

Solution

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
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<<"index :"<<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
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 `

, 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
RandomAccessIt search(RandomAccessIt begin, RandomAccessIt end, int key)
{
    RandomAccessIt last = std::prev(end);

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

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

        if ( *begin = *begin && key  *middle && key <= *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
RandomAccessIt search(RandomAccessIt begin, RandomAccessIt end, LessThanComparable key);

Code Snippets

template<typename RandomAccessIt>
int search(RandomAccessIt begin, RandomAccessIt end, int key);

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

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

    std::cout<<"index :"<<index;
}

template<typename RandomAccessIt>
RandomAccessIt search(RandomAccessIt begin, RandomAccessIt end, int key);

return std::next(begin, middle_index);

Context

StackExchange Code Review Q#91878, answer score: 7

Revisions (0)

No revisions yet.