Binary Search

Recursive Implementation of Binary Search

This article is the extension of the last article “Binary Search Algorithm” in which we have covered the basic idea around binary search and how its works along with the Recursive Implementation of Binary Search.

In this article, you will learn the implementation of Binary search in different languages like Python, Java, and C++. You will also be able to understand the time complexity analysis of Binary Search.

Recursive Implementation of Binary Search

Python

# Binary Search in python


def binarySearch(array, x, low, high):

    if high >= low:

        mid = low + (high - low)//2

        # If found at mid, then return it
        if array[mid] == x:
            return mid

        # Search the left half
        elif array[mid] > x:
            return binarySearch(array, x, low, mid-1)

        # Search the right half
        else:
            return binarySearch(array, x, mid + 1, high)

    else:
        return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

Java

/ Binary Search in Java

class BinarySearch {
  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;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int array[] = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;
    int x = 4;
    int result = ob.binarySearch(array, x, 0, n - 1);
    if (result == -1)
      System.out.println("Not found");
    else
      System.out.println("Element found at index " + result);
  }
}

C++

// 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, 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);
}

Time and Space Complexity Analysis

The time complexity of binary search can be analyzed using the number of comparisons required to find the target item. Each comparison reduces the size of the search space in half, so the number of comparisons required to find the target item is proportional to the logarithm of the size of the list.

See also  Data Structures and Algorithms | C++ STLs

The logarithm function is a mathematical function that grows much more slowly than the size of the input. For example, the logarithm of 10^6 (1 million) is just 20. So, even though the size of the list can be very large, the number of comparisons required to find the target item is small.

In mathematical terms, the time complexity of binary search can be expressed as O(log n), where n is the size of the list. This means that the number of comparisons required to find the target item grows logarithmically with the size of the list.

The Best Time Complexity of Binary Search is O(1) when the search element is the middle of the list.

The Worst time complexity of binary search is O(logN) when the search element is the first element or the last element in the list or in some cases it is not present in the list.

The space complexity of binary search is O(1), it requires a constant amount of additional memory space. This is because binary search only requires a few variables to keep track of the search space, such as the start and end indices of the current search interval, and the middle index calculated in each iteration.

That is all for this article, Happy Learning!

Leave a Comment

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

we provide projects, courses, and other stuff for free. in order for running we use Google ads to make revenue. please disable adblocker to support us.