Binary Search Algorithm- Fundamentals, Implementation and Analysis

Binary Search Algorithm and its Implementation

In our previous tutorial we discussed about Linear search algorithm which is the most basic algorithm of searching which has some disadvantages in terms of time complexity, so to overcome them to a level an algorithm based on dichotomic (i.e. selection between two distinct alternatives) divide and conquer technique is used i.e. Binary search algorithm and it is used to find an element in a sorted array (yes, it is a prerequisite for this algorithm and a limitation too).

In this algorithm we use the sorted array so as to reduce the time complexity to O(log n). In this, size of the elements reduce to half after each iteration and this is achieved by comparing the middle element with the key and if they are unequal then we choose the first or second half, whichever is expected to hold the key (if available) based on the comparison i.e. if array is sorted in an increasing manner and the key is smaller than middle element than definitely if key exists, it will be in the first half, we chose it and repeat same operation again and again until key is found or no more elements are left in the array.

Recursive Pseudocode:

// initially called with low = 0, high = N – 1
  BinarySearch_Right(A[0..N-1], value, low, high) {
      // invariants: value >= A[i] for all i < low
                     value < A[i] for all i > high
      if (high < low)
          return low
      mid = low +((high – low) / 2) // THIS IS AN IMPORTANT STEP TO AVOID BUGS
      if (A[mid] > value)
          return BinarySearch_Right(A, value, low, mid-1)
      else
          return BinarySearch_Right(A, value, mid+1, high)
  }

Iterative Pseudocode:

 BinarySearch_Right(A[0..N-1], value) {
        low = 0
        high = N - 1
        while (low <= high) {
            // invariants: value >= A[i] for all i < low
                           value < A[i] for all i > high
            mid = low +((high – low) / 2) // THIS IS AN IMPORTANT STEP TO AVOID BUGS
            if (A[mid] > value)
                high = mid - 1
            else
                low = mid + 1
        }
        return low
    }

Asymptotic Analysis

Since this algorithm halves the no of elements to be checked after every iteration it will take logarithmic time to find any element i.e. O(log n) (where n is number of elements in the list) and its expected cost is also proportional to log n provided that searching and comparing cost of all the elements is same

Data structure used -> Array
Worst case performance -> O(log n)
Best case performance -> O(1)
Average case performance -> O(log n)
Worst case space complexity -> O(1)

So the idea is-

1. Compare the key (element to be searched) with the mid element.
2. If key matches with middle element, we return the mid index.
3. Else If key is greater than the mid element, then key can only lie in right half subarray after the mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half until there are no more elements left in the array.

RECURSIVE Implementation of Binary search in C programming language

#include <stdio.h>

// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid = l + (r - l)/2;

        // If the element is present at the middle itself
        if (arr[mid] == x)  return mid;

        // If element is smaller than mid, then it can only be present
        // in left subarray
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);

        // Else the element can only be present in right subarray
        return binarySearch(arr, mid+1, r, x);
   }

   // We reach here when element is not present in array
   return -1;
}

int main(void)
{
   int arr[] = {2, 3, 4, 5, 10, 15, 25, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int x = 15;
   int result = binarySearch(arr, 0, n-1, x);
   (result == -1)? printf("Element is not present in array")
                 : printf("Element is present at index %d", result);
   return 0;
}

Output:-

Element is present at index 5

ITERATIVE Implementation of Binary search in C programming language

#include <stdio.h>

// A iterative binary search function. It returns location of x in
// given array arr[l..r] if present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
  while (l <= r)
  {
    int m = l + (r-l)/2;

    if (arr[m] == x) return m;  // Check if x is present at mid

    if (arr[m] < x) l = m + 1; // If x greater, ignore left half

    else r = m - 1; // If x is smaller, ignore right half
  }
  return -1; // If this line executes, then search was unsuccessful i.e. element is not present
}

int main(void)
{
   int arr[] = {2, 3, 4, 5, 10, 15, 25, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int x = 15;
   int result = binarySearch(arr, 0, n-1, x);
   (result == -1)? printf("Element is not present in array")
                 : printf("Element is present at index %d", result);
   return 0;
}

Output:-

Element is present at index 5

Implementation of BinarySearch(Iterative and Recursive methods) in Java

In Java Binary Search method is already implemented and it is recommended that we should use java.util.Arrays.binarySearch(//A lot of overloaded functions). See complete list of functions here – Oracle – java.util.Arrays

package com.codingeek.algorithms;

public class RecursiveBinarySearchAlgorithm {

    public static int recursiveBinarySearch(int[] sortedArray, int start, int end, int key) {

        if (start < end) {
            int mid = start + (end - start) / 2;
            if (key < sortedArray[mid]) {
                return recursiveBinarySearch(sortedArray, start, mid, key);

            } else if (key > sortedArray[mid]) {
                return recursiveBinarySearch(sortedArray, mid+1, end , key);

            } else {
                return mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {

        int[] arr1 = {2,45,100,190,280,500,670,700,999};
        int index = recursiveBinarySearch(arr1,0,arr1.length,45);
        if(index != -1){
        	System.out.println("Found 45 at "+index+" index");
        }
        else{
        	System.out.println("Element not found");
        }

        index = recursiveBinarySearch(arr1,0,arr1.length,99);
        if(index != -1){
        	 System.out.println("Found 999 at "+index+" index");
        }else{
        	System.out.println("Element not found");
        }
    }
}

Output:-

Found 45 at 1 index
Element not found

IMPORTANT NOTE :- One important point was that while finding the mid-point we do (mid = low +((high – low) / 2)) while this can also be achieved by simply doing (mid =(high + low) / 2)). This is because if both the numbers i.e. low and high are too high such that their sum reaches above the range of datatype used then it will produce an error as it will become a negative number and no array index of negative value is possible.

For ex – if low = 32,000 and high = 32,700 then
mid = (32000 + 32700)/2 = 64700/2
In C Language => 64700 for an “int” type is equal to (-835)
i.e. (-835)/2 = (-417), which will produce error.

So to avoid such situations we add the half of difference between the two to the lower value which ensures that we never encounter such a situation.

Do share the wisdom and motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.

Keep Learning.. Happy Learning.. 🙂

Recommended -