Binary Search Algorithm Implemented in C++

Binary Search also known as the half-interval search algorithm is a  type of Divide and Conquer Algorithm. It is a fairly simple algorithm in that the key element to be found is searched with a logic that is determined by the element present in the middle of the list of all elements to be found. All the elements have to be arranged in ascending or descending order for this algorithm to work. The simple logic used is checking if the value is greater or lesser than the middle element. If the value is lesser than the key element, then we check the left series of elements. If the middle value is greater than the key element, then it implies that the value to be found must be present in the right series of the list. This case happens in an increasing numbered list i.e. ascending ordered list. In a descending ordered list, the searching changes direction i.e. if lower value is required we go to the right of the series and higher value is present on the left of the series. 

The C++ code uses the elements of the list stored in an array, specifically an integer array. In our code below, we assume that the ordered list of elements are stored in the array and present in ascending order. The middle element of this array will be checked for every time that will divide this array into two different sub-arrays i.e. left sub-array and right sub-array  If the key to be found is lower than the middle element, then we search with the same technique in the left subarray and if greater then we search in the right sub-array. See the C++ code below followed by the source code:

#include <iostream>

using namespace std;

int main()
{
   int c, first, last, middle, n, Key, array[100];

   cout << "Enter number of elements\n";
   cin >> n;

   cout << "Enter " << n << " integers\n";

   for ( c = 0 ; c < n ; c++ )
      cin >> array[c];

   cout << "Enter Key Value to Search\n";
   cin >> Key;

   first = 0;
   last = n - 1;
   middle = (first+last)/2;

   while ( first <= last )
   {
      if ( array[middle] < Key )
      {
          first = middle + 1;
      }

      else if ( array[middle] == Key )
      {
         cout << Key << " is found at location " <<  (middle+1);
         break;
      }
      else
        {
            last = middle - 1;
        }


      middle = (first + last)/2;
   }

   if ( first > last )
      cout << "Element Not Present!! \n";
      cout << Key <<" is not present in the Array.\n";

   return 0;
}

Download Source Code Here. Notice that the C++ Souce Code is written in Code::Blocks 12.11 IDE available for direct download Here.

Please ask your questions and list your suggestions below in the comments section.