Write a Binary Search Program in C++ With Example?

Siva bala subramaniam | 357 Views | c++ | 15 Aug 2016

 

  • In C++ the binary search algorithm will be only applied for only a sorted array. We cannot apply it on an unsorted array. So initially we have to sort the array element.

Binary Search Algorithm C++

  • Binary search algorithm in C++ relies on a divide and conquer strategy to find a value within an already-sorted collection.

  • Binary search locates the position of an item in a sorted array.

  • Binary search compare an input search key to the middle element of the array and the comparison determines whether the element equals the input, less than the input or greater.

  • The return value is the element position in the array.
Working Flow OF Binary Search :
  • Firstly the middle element of array is found and compared with value which user wanted to search in an array.
      • If they are same then it will return the location of the required value.
      • If they are not equal then it will break the array in half.
  • If the middle element of array is smaller than the required number then it will search the first half of an array.
  • If the middle element of array is greater than the required number then it will search the second half of an array.
  • This process will continue until the required value is found or until the loop terminates or complete without founding the required value.
Binary Search Algorithm complexity :
  1. Worst case performance O(log n)
  2. Best case performance O(1)
  3. Average case performance O(log n)
  4. Worst case space complexity O(1)

Example :

#include<iostream.h>
#include<conio.h>
void main()
{
 int a[100],m,n,i,j,temp;
 void binary(int a[100],int m,int n);
 clrscr();
 cout<<"Enter the size of array";  / get the size of the array
 cin>>m;
 cout<<"Enter array element";  / input value of the array
 for(i=1;i<=m;i++)
 {
  cin>>a[i];
 }
 for(i=1;i<=m;i++)
 {
  for(j=i+1;j<=m;j++)  / sorting the number
  {
   if(a[i]>a[j])
   {
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
   }
  }
 }
 cout<<"Sorted array";  / Display the sorted array
 for(i=1;i<=m;i++)
 {
  cout<<a[i];
 }
 cout<<"Enter the search element";
 cin>>n;
 binary(a,m,n);  / call the function binary
 getch();
}
void binary(int a[100],int m,int n)  /binary search logic
{
 int low=1,high=m,mid,flag=0;
 while(low<=high&&flag==0)
 {
  mid=(low+high)/2;
  if(n==a[mid])
 {
  flag=1;
  cout<<"The number is found in "<<mid<<"position";
 }
 else if(n>a[mid])
 {
  low=mid+1;
 }
 else
 {
  high=mid-1;
 }
}
if(flag==0)
{
cout<<"The number is not found";
}
}

Output :

Enter the size of array: 5
Enter array element:
31
15
20
18
10
Sorted array:
10 
15 
18 
20 
31 
Enter the search element: 18
The number is found in 3 position
Enter the search element: 9
The number is not found