C++ program for binary search

In this example, you will learn a C++ program for the binary search algorithm. This program finds the position of the target value within the sorted array list. 

How does Binary search work?

In binary search, elements are searched from the middle of an array. It is applicable only on sorted arrays even in ascending or descending order.  If the array list is not sorted the first task is to sort it. Let’s look at an example below.

Example: Binary search program in C++

//C++ program for binary search
#include<iostream>
using namespace std; 
int main()
{
int totalNum, x,first, last, middle, arraylist[50], searchNum;
cout<<"Enter Maximum number size: ";
cin>>totalNum;
cout<<"Enter all the numbers:"<<endl;
for (x=0; x<totalNum; x++)
{
cin>>arraylist[x];
}
cout<<"Search number from the list: ";
cin>>searchNum;
first = 0;
last = totalNum-1;
middle = (first+last)/2;
while (first <= last)
{
if(arraylist[middle] < searchNum)
{
first = middle + 1;
}
else if(arraylist[middle] == searchNum)
{
cout<<searchNum<<" Found at the list.";
break;
}
else
{
last = middle - 1;
}
middle = (first + last)/2;
}
if(first > last)
{
cout<<"Number not found.";
}
return 0;
}

Output 1

cpp program for binary search if not found

Output 2

cpp program for binary search if found

Description and working of this program

  • Take the total number of array elements and their values from the user like 11, 17, 18, 45, 50, 71, 95
  • Ask the user to enter the target element.  Search =5
  • In binary search, elements are searched from the middle of an array. In the above image L=0 and H=6 so the middle of an array will be 3.
  • Now check three conditions. 1) is search element “50” equals to the middle value”45” if equals display result immediately without further proceeding if not check next condition.  2) If search element “50” is less than the middle value “45” 1st half will be treated. 3) If the search element is greater than the middle element “45” 2nd half will be treated. In the above case, the second half will be treated first because “50” is greater than “45”.
  • Similarly, the above three checks will continue until L (lower) and H (higher) become the same. If both become the same it means that the program finds the searched element and displays its array location on the screen.
  • End

Recommended Articles

C++ student grade program

C++ program to print star patterns