C++ Program for Binary Search

This C++ program searches the entered number in the list of numbers using binary search algorithm and returns the location of the input number if it is found in the list.

Example: Binary Search Program in C++

Binary search algorithm searches the target value within a sorted array.

• To perform a binary search array must be sorted, it should either be in ascending or descending order.
• Step 1: First divide the list of elements in half.
• Step 2: In the second step we compare the target value with the middle element of the array. If it matches the middle element then search ends here and doesn’t proceed further.
• Step 3: Else if the element less than the middle element then we begin the search in lower half of the array.
• Step 4: Else if the element is greater than the middle element then we begin the search in greater half of the array.
• Step 5: We will repeat the steps 3 ,4 and 5 until our target element is found.

#include <iostream>
using namespace std;

int binarySearch(int[], int, int, int);

int main()
{
   int num[10] = {10, 22, 37, 55, 92, 118};
   int search_num, loc=-1;

   cout<<"Enter the number that you want to search: ";
   cin>>search_num;

   loc = binarySearch(num, 0, 6, search_num);

   if(loc != -1)
   {
      cout<<search_num<<" found in the array at the location: "<<loc;
   }
   else
   {
      cout<<"Element not found";
   }
   return 0;
}

int binarySearch(int a[], int first, int last, int search_num)
{
   int middle;
   if(last >= first)
   {
      middle = (first + last)/2;
      //Checking if the element is present at middle loc
      if(a[middle] == search_num)
      {
         return middle+1;
      }

      //Checking if the search element is present in greater half
      else if(a[middle] < search_num)
      {
         return binarySearch(a,middle+1,last,search_num);
      }

      //Checking if the search element is present in lower half
      else
      {
         return binarySearch(a,first,middle-1,search_num);
      }

   }
   return -1;
}

Output:

Enter the number that you want to search: 55
55 found in the array at the location: 4