Binary Search

1. Binary Search Algorithm
2. Binary Search Example
3. Binary Search Algorithm Implementation
4. Binary Search Algorithm Complexity

Binary search is the most popular and efficient searching algorithm. In fact, it is the fastest searching algorithm. Just like jump sort, it also needs the array to be sorted. It is based on the divide and conquer approach in which we divide the array into two halves and then compare the item we are searching with the middle item. If the middle item matches, we return the middle element’s index; otherwise, we move to the left and right half depending on the item’s value.

Binary Search Algorithm

Let us assume that we have an unsorted array A[] containing n elements, and we want to find an element X.

Binary Search Example

Suppose we have the array: (1, 2, 3, 4, 5, 6, 7, 8, 9), and we want to find X - 8.

Binary Search Algorithm Implementation

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

int main(void) {
  int n = 9;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 8;
  int result = binarySearch(arr, 0, n - 1, x);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

Binary Search Algorithm Complexity

Time Complexity

• Average Case

When we perform the binary search, we search in one half and discard the other half, reducing the array’s size by half every time.

The expression for time complexity is given by the recurrence.

T(n) = T(n/2) + k , k is a constant.

This result of this recurrence gives logn, and the time complexity is of the order of O(logn). It is faster than both linear search and jump search.

• Best Case

The best-case occurs when the middle element is the element we are searching for and is returned in the first iteration. The best-case time complexity is O(1).

• Worst-Case

The worst-case time complexity is the same as the average-case time complexity. The worst-case time complexity is O(logn).

Space Complexity

This algorithm’s space complexity is O(1) in the case of iterative implementation because it doesn’t require any data structure other than temporary variables.

In the case of recursive implementation, the space complexity is O(logn) due to the space required by the recursive calls stack.