C++ Program to implement binary search

In this program, you’ll learn how to implement a binary search tree.

The working of Binary Search:

In a binary search, it looks for a particular item by comparing the middlemost item of the collection. If a match is found, then the index of an item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item.

Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.

Program to implement binary search

#include<iostream>
 using namespace std;

  // Prototypes of Functions
  void bubbleSort(int array[], int size);
  bool binarySearch(int array[], int size,int key);

  int main(){
      cout<<"Enter any 5 numbers : "<<endl;

      // Size can be change by replacing 5
      int array[5]; //Declaring array
     for(int i=0; i<5; i++)
      {
       cout<<"\t";  cin>>array[i]; // Initializing array
      }

      //Passing Arrary for Sorting
       bubbleSort(array,5);

    // Array has Sorted At This Point
    cout<<"\n\t\t\tEnter no to be searched : ";
    int key;
    cin>>key;

//Passing Array, size and key To Search Key
int result=binarySearch(array,5,key);

if(result==1)
cout<<"\n\t\t\tNumber found in array "<<endl;
else
cout<<"\n\t\t\tNumber 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++)
      {
       //Displaying Array
       cout<<"\t\t\tValue at "<<j<<" Index: "<<array[j]<<endl;
      }
      cout<<endl;
    // Bubble Sort Starts Here
     int temp;
     for(int i2=0; i2<size; i2++)
   {
     for(int j=0; j<size-1; j++)
     {
        //Swapping element in if statement
           if(array[j]>array[j+1])
       {
        temp=array[j];
        array[j]=array[j+1];
        array[j+1]=temp;
       }
     }
   }
   // Displaying Sorted array
      cout<<"  Sorted Array is: "<<endl;
     for(int i3=0; i3<size; i3++)
   {
    cout<<"\t\t\tvalue at "<<i3<<" index is : "<<array[i3]<<endl;
   }
}// Sort Function Ends Here

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;
     }// While Loop End

   if(array[mid]==key)
    return true; //Returnig to main
    else
   return false;//Returnig to main

   cout<<"\n\n\n";
}// binarySearch Function Ends Here

Output

Enter any 5 numbers:
		     5
		     -17
		     15
		     3
		     0
Input array is:
		value at 0 index is : 5
		value at 1 index is : -17
		value at 2 index is : 15
		value at 3 index is : 3
		value at 4 index is : 0
sorted array is:
		value at 0 index is : -17
		value at 1 index is : 0
		value at 2 index is : 3
		value at 3 index is : 5
		value at 4 index is : 15

Enter no to be searched : 15

Number found in array

Time Complexity for Selection Sort

Best-case performance	O(1)
Average performance	O(log n)
Worst-case space complexity	O(1)

Related Programs

Ask your questions and clarify your/other doubts on the program to implement a binary search by commenting. Documentation.