Binary Search : - Binary Search is a searching algorithm for finding a element's position in that respective sorted array. This search algorithm works on the principle of divide and conquer.

Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of 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.

Binary Search algorithm can be implement by two ways : -

1. Iterative Method
2. Recursive Method

Let's look into it's iterative method first -

// Implementation of Binary Search in C++

#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {

    // Repeat until the pointers low and high meet each other
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
}

Now, let's look into it's recursive method -

// Implementation of Binary Search in C++

#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;

    // If found at mid, then return it
    if (array[mid] == x)
      return mid;

    // Search the left half
    if (array[mid] > x)
      return binarySearch(array, x, low, mid - 1);

    // Search the right half
    return binarySearch(array, x, mid + 1, high);
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
}

Deriving the time complexity of Binary Search Algorithm : -

Base Case Time Complexity -

The best case of Binary Search occurs when the element to be search is in the middle of the list.

In this case, the element is found in the first step itself and this involves 1 comparison.

Therefore, the best case time complexity of Binary Search will be O(1).

Average Case Time Complexity : -

Let there be N distinct numbers: a1, a2, ..., a(N-1), aN

We need to find element P.

There are two cases:

Case 1: The element P can be in N distinct indexes from 0 to N-1.

Case 2: There will be a case when the element P is not present in the list. There are N case 1 and 1 case 2. So, there are N+1 distinct cases to consider in total.

If element P is in index K, then Binary Search will do K+1 comparisons.

This is because:

The element at index N/2 can be found in 1 comparison as Binary Search starts from middle.

Similarly, in the 2nd comparisons, elements at index N/4 and 3N/4 are compared based on the result of 1st comparison.

On this line, in the 3rd comparison, elements at index N/8, 3N/8, 5N/8, 7N/8 are compared based on the result of 2nd comparison.

Based on this, we know that:

Elements requiring 1 comparison: 1 Elements requiring 2 comparisons: 2 Elements requiring 3 comparisons: 4 Therefore, Elements requiring I comparisons: 2^(I-1)

The maximum number of comparisons = Number of times N is divided by 2 so that result is 1 = Comparisons to reach 1st element = logN comparisons

I can vary from 0 to logN

Total number of comparisons = 1 * (Elements requiring 1 comparison) + 2 * (Elements requiring 2 comparisons) + ... + logN * (Elements requiring logN comparisons)

Total number of comparisons = 1 * (1) + 2 * (2) + 3 * (4) + ... + logN * (2^(logN-1))

Total number of comparisons = 1 + 4 + 12 + 32 + ... = 2^logN * (logN - 1) + 1

Total number of comparisons = N * (logN - 1) + 1

Total number of cases = N+1

Therefore, average number of comparisons = ( N * (logN - 1) + 1 ) / (N+1)

Average number of comparisons = N * logN / (N+1) - N/(N+1) + 1/(N+1)

The dominant term is N * logN / (N+1) which is approximately logN.

Therefore, Average Case Time Complexity of Binary Search is O(logN).

Worst Case Time Complexity : -

The worst case of Binary Search occurs when the element is to search is in the first index or last index.

In this case, the total number of comparisons required is logN comparisons.

Therefore, Worst Case Time Complexity of Binary Search is O(logN).

Conclusion : -

• Best Case Time Complexity of Binary Search: O(1)

• Average Case Time Complexity of Binary Search: O(logN)

• Worst Case Time Complexity of Binary Search: O(logN)