Search key in a rotated sorted array without repetition of elements

Question

Is there any improvement possible in this implementation?

#include<iostream>
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 [ middle_index ] )
 {
 if( key >= array[ first_index ] && key < array [ middle_index ] )
 last_index = middle_index - 1;
 else
 first_index = middle_index + 1; 
 }
 else
 { 
 if( 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;
}

• Morwenn: I used a bit of C++11 in my answer, are you fine with it?
• Steephen: @Morwenn sure, it is most welcome. Thanks for the review.
• Morwenn: Good then. Now I remember already having answered some of your questions in the past and you indeed used modern C++. I should have again before asking :)
• ruds: You have a typo in the initialization of middle_index, which requires parentheses.

Answer 1

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<typename RandomAccessIt>
  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<typename RandomAccessIt>
  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 <iterator>, 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<typename RandomAccessIt>
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 < *middle )
 {
 if( key >= *begin && key < *middle )
 last = std::prev(middle);
 else
 begin = std::next(middle); 
 }
 else
 { 
 if( 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<typename RandomAccessIt, typename LessThanComparable>
RandomAccessIt search(RandomAccessIt begin, RandomAccessIt end, LessThanComparable key);

• user1118321: Excellent point about using iterators!
• Morwenn: Also, I may have off-by-one errors. You may have to check the code thoroughly to make sure it always works as intended.

Answer 2

Overall, I think this looks really good. It's a straightforward implementation that is easy to understand and has a decent running time.

If I were being nitpicky, I'd probably do the following:

1. Make the arguments to the search() function const. They aren't going to change, so let the compiler and caller know that.
2. Name the arguments in a meaningful way. N should be something more clear like numberOfElements. Also, making it uppercase makes it look like a macro or #defined constant.
3. Speaking of constants, the return value of -1 should probably be a named constant such as VALUE_NOT_FOUND or something like that.
4. I'm not fond of the names first_index and last_index since they change. The first index of the array is always 0, and the last index of the array is always N-1, so I'd prefer to see names like low_index and hi_index or something of that sort.

If I were being extra-nitpicky, I'd say that this is C++ and you shouldn't be using standard C-style arrays. The numbers should be in a container like std::vector. If you did that, you wouldn't need to pass N, either, as you'd just check the container's size.