Binary Search in C++

May 15, 2025

What is binary search in C++?

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 an efficient and fast searching algorithm.

  • 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.
binary search in c++ programming

How Binary Search Works in C++ (Simple Explanation):

  1. The list must be sorted in either ascending or descending order.
  2. Calculate the middle index using a formula.
  3. If the target element matches the middle element, the search stops.
  4. If the target is greater than the middle element, search the right half of the list.
  5. If the target is smaller, search the left half of the list.
  6. Repeat steps 3, 4, and 5 until the element is found or the list is fully checked.

Space and Time Complexity

Time Complexity (Best)Ω(1)
Time Complexity (Avg)Θ(log n)
Time Complexity (Worst)O(log n)
Space ComplexityO(1)
Binary-Search-in-C++-Language

Algorithm for Binary Search

  • while(left<=right)
          mid=left + (right – left)/2;
  • if(a[mid]<item)
          left=mid+1;
  • else if(a[mid]>item)
          right=mid-1;
  • If found return index+1
  • Else return -1

Methods Discussed Here:

We will take a look at two different approaches

  1. Recursive Approach
  2. Iterative Approach

1. Binary Search (Recursive Approach)

Run 
// Binary Search implimentation in C++ (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
#include<bits/stdc++.h>
using namespace std;

int binarySearch(int array[], int left, int right, int item){
    
    if (right >= left){
        
        // calculation of new mid
        int mid = left + (right - left)/2;

        // returns position where found
        if (array[mid] == item)
            return mid+1;
        
        // goes to recursive calls in left half
        if (array[mid] > item)
            return binarySearch(array, left, mid-1, item);
    
        // goes to recursive calls in right half
        else
            return binarySearch(array, mid+1, right, item);
    }
    // if element is not found we return -1
    else
       return -1;
}
int main(){
 
    int array[10] = {3, 5, 7, 9, 12, 15, 16, 18, 19, 22};
    int item = 15;
   
    int position = binarySearch(array, 0, 10, item);

    if(position == -1)
        cout<<"Not Found";
    else
        cout<<"We found the item "<< item <<" at position "<< position;
}

Output:

We found the item 15 at position 6

2. Binary Search (Iterative Approach)

This one is simple too let’s have a look at this approach to solve binary search.

Run

// Binary Search implimentation in C++ (Iterative)
// Time Complexity : O(N)
// Space Complexity : O(1)
#include<bits/stdc++.h>
using namespace std;

// Returns index of item in given array, if it is present
// otherwise returns -1
int binarySearch(int arr[], int l, int r, int item)
{
    while (l <= r) {
        int mid = l + (r - l) / 2;
  
        // if item is at mid
        if (arr[mid] == item)
            return mid;
  
        // If item greater, ignore left half, consider only right half
        if (arr[mid] < item)
            l = mid + 1;
  
        // If item is smaller, ignore right half, consider only left half
        else
            r = mid - 1;
    }
  
    // if we are able to reach here
    // means item wasn't present
    return -1;
}
  
int main()
{
    // array needs to be sorted to impliment binary search
    int arr[] = {3, 5, 7, 9, 12, 15, 16, 18, 19, 22};
    int n = sizeof(arr) / sizeof(arr[0]);
    int item = 7;
    
    int position = binarySearch(arr, 0, n - 1, item);
    
    if(position == -1)
        cout << item << " Not Found";
    else
        cout << item << " Found at index " << position;
        
    return 0;
}

Output

7 Found at index 2

Advantages and Disadvantages of Binary Search

AdvantagesDisadvantages
Efficient for large, sorted datasets; Reduces search space by half in each step; Time complexity of O(log N).Requires the data to be sorted beforehand.
Simple implementation using iterative or recursive approach.Not suitable for unsorted data; Additional sorting step increases overall time complexity.
Optimized for search operations in sorted arrays.Recursive implementation can cause stack overflow for large datasets.

You can also study binary search in C and Java:

C Language | Java Language

You can also study binary search in C and Java:

C Language | Java Language

Binary Search in C++ Meme 1

FAQ's Related to Binary Search In C++

Answer:

Binary Search is a search algorithm that repeatedly divides a sorted array in half to locate a target value. It has a time complexity of O(log N).

Answer:

Use Binary Search when the dataset is sorted and you need to quickly find an element with minimal comparisons.

Answer:

Binary Search requires the dataset to be sorted beforehand. It is not suitable for unsorted data without sorting it first.

Answer:

The iterative approach uses a loop to search for the target, while the recursive approach uses function calls, which can lead to stack overflow for large datasets.