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
Output 2
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