Binary Search in C++

Binary search program in C++ Programming Language. Binary search in C++ is an efficient algorithm for finding an item from a sorted list or array of items. Sometimes it is also known as half-interval search, logarithmic search, or binary chop. 

Condition to use binary search:- The array must be sorted.

The binary search algorithm cannot be applied to unsorted arrays. This algorithm can be used when the array has terms occurring in order of increasing size (for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in lexicographic, or alphabetic, order). If the array or list is not sorted then before applying the binary search algorithm, first sort the array or list.

The binary search algorithm can be written in two ways. These are,
a) Recursive approach
b) Iterative approach

Binary Search in C++ using Recursion

In the recursive approach, the recursion technique is used. It is an example of the divide and conquers technique where bigger problems are divided into smaller problems. Like all divide and conquer algorithms binary search first divide the large array into smaller sub-arrays and then solve it recursively.  It us see it in detail.

Binary Search Algorithm in C++ using Recursive Approach

a) Take an array, initial index, size, and search key.
b) Find the middle term.
c) if middle term == search key then return index.
d) if middle term > search key then apply recursive call on the first half of the array.
e) else apply recursive call on the second half of the array.
f) Repeat the process until the search key not matched.
g) If not matched then return -1.

It can be written as,

int binarySearch(arr, low, high, key) {
    if (high >= low) {
        int mid = low + (high - low) / 2; 
        if (arr[mid] == key) return mid; 
        if (arr[mid] > key) 
            return binarySearch(arr, low, mid - 1, key); 
        return binarySearch(arr, mid + 1, high, key); 
    }
    return -1; 
}

The time complexity of this algorithm = O(log n)

How Recursive approach works?

In binary search using the recursive approach, we split the array from the middle into two subarrays of the same size or where one of these smaller lists has one fewer term than the other. Let us understand it through an example.

Array = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

Example

Assume the search term = 40. Then the steps in binary search,

• Find the middle term of the array. If the size of array is odd then middle-index = (size – 1)/2 else middle-index = size/2. In our example, middle index = 10/2 = 5, and middle term is array[3] = 60
• Compare middle term and search term. If the middle term > search term then it may exist in the first portion of the array else in the second portion of the array. Since 60 > 40 therefore search term may exist only in the first portion of the array.
• Split the array into two parts from the middle index. The subarr1 = {10, 20, 30, 40, 50} and subarr2 = {60, 70, 80, 90, 100}.
• Since the array is sorted and 60 > 40, therefore search terms may exist only in the first sub-array. Forgot about the second sub-array, no use of it, only the first sub-array is required for the next step. Now, assume the original array = {10, 20, 30, 40, 50}, and search term = 40.
• Repeat the same process with first sub array. Find the middle term. The middle index = (5-1)/2 = 2, middle term is array[2] = 30
• Compare middle term with the search term, 30 < 40 therefore it may exist only in the second portion.
• Split array into two subarrays from the middle index. The new sub arrays are:- subarr1 = {10, 20} and subarr2 = {30, 40, 50}. Only subarr2 will be considered for the next steps, no use of subarr1. Now, assume array = {30, 40, 50} and search term = 40. Repeat the process.
• Find middle term. The middle index = (3-1)/2 = 1 and the middle term is array[1] = 40.
• Compare middle term and search term. Currently, both are equal and the match is found.

C++ program to implement binary search using Recursion

Now let us see the implementation of the binary search algorithm in the C++ programming language. Here the function binarySearch() finds the index of the search key, if the match is found then it returns the index of the search key else it returns -1.

#include<iostream>
using namespace std;
// recursive function for binary search
/* if match found then return index of search key
   else return -1 */
int binarySearch(int arr[], int low, int high, int key) {
  if (high >= low) {
    // find middle index
    int mid = low + (high - low) / 2; 
     
    // find middle term and compare
    if (arr[mid] == key) return mid; // key found 
     
    // If key is smaller than middle term, then 
    // it can only be present in left subarray 
    if (arr[mid] > key) 
      return binarySearch(arr, low, mid - 1, key); 
    
    // Else the key can only be present 
    // in right subarray 
    return binarySearch(arr, mid + 1, high, key); 
  } 
     
  // key not found
  return -1; 
}

// main function
int main()
{
  int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
  int key = 0;

  // take input for the search key
  cout << "Enter Search Element: ";
  cin >> key;

  // find the size array
  int size = sizeof(array)/sizeof(array[0]);

  // search key
  int index = binarySearch(array, 0, size, key);
  
  // display result
  if(index == -1)
    cout << key << " Not Found" << endl;
  else
    cout << key << " Found at Index = " << index << endl;

  return 0;
}

Output:-

Enter Search Element: 90
90 Found at Index = 8

Enter Search Element: 99
99 Not Found

Binary Search in C++ using Iterative approach

In this approach, instead of calling the method recursively, we use iteration to traverse the array and find the search key. Both approaches are quite the same, with two differences in implementation. 

In the recursive method, there is no loop, and rather than passing the new values to the next iteration of the loop, it passes them to the next recursion. In the iterative method, the iterations can be controlled through the looping conditions, while in the recursive method, the maximum and minimum are used as the boundary condition. 

Algorithm

To search for the integer x in the list/array a₁, a₂ , … ,a_n , where list/array is in ascending order (a₁ < a₂ <  ··· < a_n) , 

• begin by comparing x with the middle term a_m of the list/array, where m = ⌊(n + 1)/2⌋. 
• If x > a_m, the search for x is restricted to the second half of the list, which is a_m+1, a_m+2, …, a_n.
• If x is not greater than a_m , the search for x is restricted to the first half of the list, which is a₁, a₂, …, a_m.
• The search has now been restricted to a list with no more than ⌊n/2⌋ elements. 
• Using the same procedure, compare x to the middle term of the restricted list. 
• Then restrict the search to the first or second half of the list. 
• Repeat this process until a list with one term is obtained. 
• Then determine whether this term is x.

The algorithm can be written as,

int binarySearch(int arr[], int low, int high, int key) {
  int i = low; // left index
  int j = high; // right index
  int mid = 0;

  while(i < j) {
    // find middle index
    mid = (i+j) / 2;

    // compare search key and middle term
    if(key > arr[mid]) 
      i = mid + 1;
    else
      j = mid;
  }
      
  // when i==j
  if(key == arr[i]) 
    return i; // key found

  return -1; // key not found 
}

Program

C++ program for binary search using iterative approach,

#include<iostream>
using namespace std;
// function for binary search
/* if match found then return index of search key
   else return -1 */
int binarySearch(int arr[], int low, int high, int key) {
  int i = low; // left index
  int j = high; // right index
  int mid = 0;
      
  while(i < j) {
    // find middle index
    mid = (i+j) / 2;

    // compare search key and middle term
    if(key > arr[mid]) 
      i = mid + 1;
    else
      j = mid;
  }
      
  // when i==j
  if(key == arr[i]) 
    return i; // key found

  return -1; // key not found 
}

// main function
int main()
{
  int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
  int key = 80; // search key

  // find the size array
  int size = sizeof(array)/sizeof(array[0]);

  // search key
  int index = binarySearch(array, 0, size, key);
  
  // display result
  if(index == -1)
    cout << key << " Not Found" << endl;
  else
    cout << key << " Found at Index = " << index << endl;

  return 0;
}

Output:-

80 Found at Index = 7

Binary Search Time Complexity

Best-case time complexity	O(1)	When the search key present at the center (middle term) of the array/list.
Worst-case time complexity	O(log n)	When the search key is not available or at the extremity of the list.

In the iterative method, the space complexity would be O(1). While in the recursive method, the space complexity would be O(log n). 

For the small arrays linear search algorithm gives better performance compared to the binary array, but for the large arrays if the array is in sorted order then the binary search gives better performance compared to the linear search. 

There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search