Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock
PrepInsta
Feed
Prime

Binary Search in C++

July 26, 2020

What is binary search in C++?

Binary search is another searching algorithm in C++. It is also known as half interval search algorithm. It is efficient and fast searching algorithm. If we want to search any element in the list then the only condition required is that the elements in the list must be in sorted order. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one.

introduction to binary search in c++

Working of binary search in C++

  1. The searching algorithm proceed when the list is is in sorted order either ascending or descending.
  2. Now divide the list into two halves.
  3. If the element is at the center stop searching.
  4. Else if the element is smaller then the last element of first half then further we will search in first half.
  5. And if the element is greater than the first element of second half then further we will search in second half.
  6. We will follow step 3 ,4 and 5 until our element is found.

 

Steps to implement Binary Searching with C++

  1. In the given list, first we will find the middle of the list using formula M=(L+R)/2, where  M is the index of middle element, L is the index of leftmost element and R is the index of rightmost element.
  2. If the element to be search is on the middle index then we will terminate the search as our element is found.
  3. Else we will check if the element is smaller then the middle element or greater then the middle element.
  4. If it is smaller then the middle element we will continue our search in first half.
  5. And if it greater then the middle element we will continue our search in second half.
  6. We will repeat all the previous steps until our element is found.
binary search in C++ programming language

Algorithm for Binary Search in C++

  • while(low<=high)
          mid=(low+high)/2;
  • if(a[mid]<search_element)
          low=mid+1;
  • else if(a[mid]>search_element)
          high=mid-1;
  • If found return index
  • Else return -1

C++ Program for Binary Search 

#include <iostream>//Header file.
using namespace std;

int binarySearch(int[], int, int, int); 

int main() //Main function.
{ 
  int arr[10] = {19, 26, 37, 53, 56, 61, 77, 82, 87, 91}; 
  int search_element, location=-1;

  cout<<"Enter the element which you want to search: "; 
  cin>>search_element;

  location = binarySearch(arr, 0, 9, search_element); 

  if(location != -1) 
  { 
    cout<<"Search element found at"<<location<<" location"; //Printing the result.
  } 
  else 
  { 
    cout<<"Search element not present"; 
  } 
  return 0;
} 

int binarySearch(int a[], int left, int right, int search_element) 
{ 
  int middle; 
  if(right >= left) 
  { 
    middle = (left + right)/2; 
    if(a[middle] == search_element) //Checking if elemnet is present at middle.
    { 
      return middle+1; 
    } 
    else if(a[middle] < search_element) //Checking if elemnet is present in greater half.
    { 
      return binarySearch(a,middle+1,right,search_element); 
    } 
    else //Checking if elemnet is present in samller half.
    { 
      return binarySearch(a,left,middle-1,search_element); 
    }

  } 
  return -1; 
}
Output:
Enter the element which you want to search: 53
Search element found at 4 location

Advantages of binary searching technique

Binary search has following advantage:-
  • Works faster then linear search.
  • It is a simple algorithm.
You can also study about binary search in C and Java
Binary Search in C++ Meme 1

Time Complexity
For Binary Search

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space Complexity

O(1)

Average Comparisions

Log(N+1)