4
\$\begingroup\$

In computer science, binary search, also known as half-interval search or logarithmic search, is a search algorithm that finds the position of a target value within a sorted array.

The code returns true if an element is present in the array else returns false.

Any suggestion in improving the code is welcome.

Binary_Search.h

#ifndef BINARY_SEARCH_H
#define BINARY_SEARCH_H

bool binary_search(int ar[], int low, int high, int key);

#endif // BINARY_SEARCH_H

Binary_Search.cpp

#include <iostream>
#include "Binary_Search.h"

/* search a key in an array using binary search */
bool binary_search(int ar[], int low, int high, int key)
{
  int mid;

  while ( low <= high )
    {
      // find the middle index
      mid = low + ((high - low) >> 1);

      if ( ar[mid] == key ) // key found
        {
          return true;
        }
      else if ( ar[mid] > key ) // key may be on the left half
        {
          high = mid - 1;
        }
      else if ( ar[mid] < key ) // key may be on the right half
        {
          low = mid + 1;
        }
    }

  // key not found
  return false;
}

int main()
{
  int ar[] = {1, 7, 9, 10, 28, 28, 36, 49, 68, 99};

  for ( int i = 0; i < sizeof(ar) / sizeof(ar[0]); ++i )
    {
      if ( binary_search(ar, 0, sizeof(ar) / sizeof(ar[0]) - 1, ar[i]) )
        {
          std::cout << ar[i] << " is present" << std::endl;
        }
      else
        {
          std::cout << ar[i] << " is not present" << std::endl;
        }
    }

  int ar1[] = {-1, 2, 3, 12, 23, 50, 90, 98, 100};
  for ( int i = 0; i < sizeof(ar1) / sizeof(ar1[0]); ++i )
    {
      if ( binary_search(ar, 0, sizeof(ar) / sizeof(ar[0]) - 1, ar1[i]) )
        {
          std::cout << ar1[i] << " is present" << std::endl;
        }
      else
        {
          std::cout << ar1[i] << " is not present" << std::endl;
        }
    }
  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Your formatting style looks weird and unusual. But that's actually not a point for code review, unless there are certain style guides set up. \$\endgroup\$ – πάντα ῥεῖ Jan 28 '17 at 11:44
  • \$\begingroup\$ Well if you are pointing to the braces then emacs gives that kind of formatting. I don't know whether that is good or not \$\endgroup\$ – Abhisek Jan 28 '17 at 11:53
  • \$\begingroup\$ Yes I'm talking about the brace indentation. IIRC you can choose/edit the templates emacs applies. \$\endgroup\$ – πάντα ῥεῖ Jan 28 '17 at 11:55
  • \$\begingroup\$ I'll search that, but why the default indentation behavior is strange. \$\endgroup\$ – Abhisek Jan 28 '17 at 11:59
  • \$\begingroup\$ The more usual style is that the opening brace is at the same indentation level as the conditional/loop condition statement, or starts with one blank offset after that statement, and the closing brace is always at the same indentation level as the conditional/loop condition statement. \$\endgroup\$ – πάντα ῥεῖ Jan 28 '17 at 12:02
5
\$\begingroup\$

Interface

Passing an array and then two indexes is a very C style of interface. In C++ it is much more common to pass two iterators. An iterator is a generalized form of pointer.

So rather than:

bool binary_search(int ar[], int low, int high, int key);

I would use:

template<typename I>
bool binary_search(I low, I high, int key);

Also rather than pointing at the first and last elements iterator ranges use a first and one past the last. This makes calculating sizes easier.

Code Review

Don't use >> 1 to represent a divide by 2. The point of high level code is to write it so that it is easy for humans to read. That is not obvious. Also the compiler can do these micro optimizations much better than you. So don't try and confuse it. Just write code in the most readable way possible.

Don't use sizeof(ar) / sizeof(ar[0]) it is so easy to break as array collapse into pointers at the drop of a hat. Use std::size() which works for arrays/containers but will fail to compile for pointers (which is what you want).

But if you switch to using Iterator based interface then you should use std::begin() and std::end().

Style

Your bracing style is uncommon. But not so egregious that I would complain about. Normally brace style is defined by a local style guide. So if you are in a compnany or project just check that.

 // Most common C++ styles
 if ()
 {
     Statement;
 }

 // or
 if () {
     Statement;
 }
\$\endgroup\$
  • \$\begingroup\$ "Don't use >> 1 to represent a divide by 2." More importantly, don't use a right-shift to represent a divide with a signed integer, as the behavior is undefined. To make this work correctly, you need to cast the value to an unsigned integer. Then you could legally use a shift, but as you said, you should just do a division and let the compiler optimize it. (It will.) \$\endgroup\$ – Cody Gray Jan 29 '17 at 11:55
  • \$\begingroup\$ While I agree that using an iterator interface like STL does is nicer, I wouldn't advocate using template<typename I> for a function that clearly only should accept only one specific type of iterator, namely int * in this case. \$\endgroup\$ – G. Sliepen Jan 29 '17 at 12:00
  • \$\begingroup\$ @G.Sliepen: What about vector<int> or float[] or vector<float> or std::complex<int>[] or std::vector<std::complex<int>> The interface is valid for all these types. \$\endgroup\$ – Martin York Jan 29 '17 at 16:59
  • \$\begingroup\$ @LokiAstari: sure, but maybe that is not desired? In any case, the problem was not about making a template function, and the solution does not require a template function, so by suggesting it you risk adding confusion. You also did not provide an example of how to use your template function interface. \$\endgroup\$ – G. Sliepen Jan 29 '17 at 19:51
2
\$\begingroup\$

Avoid using std::endl

Use "\n" instead. It is guaranteed to produce the correct newline character(s) on all platforms. The problem with std::endl is that it not only adds a newline, it also flushes the output stream. If you have a lot of data to write to the output, this can cause a significant slowdown.

So instead of:

std::cout << ar[i] << " is present" << std::endl;

Write the following:

std::cout << ar[i] << " is present\n";
\$\endgroup\$
0
\$\begingroup\$

If you use high past end of the array, and replace

while ( low <= high )

with

while ( low != high )

you'll be able to search descending array by initial low > high values.

\$\endgroup\$
  • 1
    \$\begingroup\$ The iterator approach suggested by another answer provides the same benefit but is more idiomatic C++ than passing an array. \$\endgroup\$ – Null Jan 30 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.