Today we will learn Binary Search Program in C++. So before getting started, we will make you know about binary search. What exactly binary search is?

What is Binary Search?

This is a very efficient searching method used for linear or sequential data (files, arrays or linked lists).

Pre-requirement: data has to be in the sorted order.

Procedure:

In this method, the set of elements is partitioned into two equal parts and the required key is compared with the key of the middle record. If a match is found, the search terminates.

linear search program in c
source:penjee.com

If the key is less than the middle key, the search proceeds in the top half of the table.

And If the key is greater than the middle key, the search proceeds in the same way in the lower half of the table.

The process continues until no more partitions are possible.

Thus every time a match is found, the remaining table size to be searched reduces the half.

Binary Search Algorithm:

1st Step: START.

2nd Step: Accept key to be searched.

3rd Step: top=0.

4th Step: bottom=n-1.

5th Step: mid= (top+bottom) / 2.

6th Step: If k(mid)==key then Display “Record found at position mid” then go to step 10.

7th Step: If key<k(mid) then bottom=mid-1 else, top=mid+1.

8th Step: If top<=bottom then go to step 5.

9th Step: Display “Record not found”.

10th Step: STOP.

Efficiency:

After 0 Comparisons -> Remaining file size = n.

After 1 Comparisons -> Remaining file size = n/2 = n/2^1.

And after 2 Comparisons -> Remaining file size = n/4 = n/2^2.

And after k Comparisons -> Remaining file size = n / 2^k.

The process terminates when no more partitions are possible i.e remaining file size = 1 -> n/2^k =1. i.e, k=log2n (2 is at base).

Thus, the time complexity is O(log2n) which is very efficient.

Example: If there are 1024 records in the file and the record with the required key is not present (worst case), the maximum number of comparisons will be log2(1024) = 10.

Advantages:

Time complexity is O(log2n) which is very efficient.

Does not require any additional data structure.

Disadvantages:

Data has to be in sorted manner.

This method can only be applied to the sequential or linear data structure.

The following program illustrates a binary search on a set of n elements. The elements are sorted using the bubble sort method studied earlier.

1. Binary Search Program in C++

In this program, the compiler will ask the user to enter the elements. After the user enters the number to find then the compiler will start to find the number in the array. If the number is found then the compiler will print the number found at position i else print number not found.

Consider high=start and low=end.

//Learnprogramo - programmming made simple
#include<iostream>
using namespace std;
void bubbleSort(int array[], int size);
bool binarySearch(int array[], int size,int key);
int main(){
cout<<"Enter any 5 numbers : "<<endl;
int array[5]; //Declaring array
for(int i=0; i<5; i++)
{
cout<<"\t";  cin>>array[i]; // Initializing array
}
bubbleSort(array,5);
cout<<"\nEnter no to be searched : ";
int key;
cin>>key;
int result=binarySearch(array,5,key);
if(result==1)
cout<<"\nNumber found in array "<<endl;
else
cout<<"\nNumber not found in array "<<endl;
return 0;
}
void bubbleSort(int array[], int size){
      cout<<"  Input array is: "<<endl;
      for(int j=0; j<size; j++)
      {
       cout<<"Value at "<<j<<" Index: "<<array[j]<<endl;
      }
      cout<<endl;
     int temp;
     for(int i2=0; i2<size; i2++)
   {
     for(int j=0; j<size-1; j++)
     {
           if(array[j]>array[j+1])
       {
        temp=array[j];
        array[j]=array[j+1];
        array[j+1]=temp;
       }
     }
   }
      cout<<"  Sorted Array is: "<<endl;
     for(int i3=0; i3<size; i3++)
   {
    cout<<"value at "<<i3<<" index is : "<<array[i3]<<endl;
   }
}
bool binarySearch(int array[],int size, int key){
         int start=1, end=size;
         int mid=(start+end)/2;
  while(start<=end&&array[mid]!=key){
        if(array[mid]<key){
          start=mid+1;
      }
     else{
          end=mid-1;
          }
       mid=(start+end)/2;
     }
   if(array[mid]==key)
    return true;
    else
   return false;
   cout<<"\n\n\n";
}

Output:

binary search program in c++

Explanation:

We first, consider in the number of components the user selection wants and keep it into n. Next, we take the components from the user. Then, we choose the amount to be hunted by the array and keep it at the key.

We assign 0 to the very low factor that’s the first indicator of an array and n-1 into the large element, that’s the previous element from the array. There’s a while loop that checks if none is significantly less then high to ensure the range still has components inside.

If low is higher afterwards, high then the selection is empty. Within the while loop, we first assess whether the component at the middle is significantly less than the primary value(array[mid] < key).

If so, we then assign reduced the worth of mid +1 since the essential value is higher then mid and can be more towards the higher side.

Also Read: