Binary Search

Binary Search Implementation and Time Complexity Analysis

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 two types of algorithms (Iterative and Recursive).

Binary Search Implementation and Time Complexity Analysis

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.

Introduction

I hope by now you have a clear understanding of what is Binary Search and the internal working of binary search. You will now look at another example of binary to understand better and then we will implement it.

Let us consider the array of elements {2,5,8,12,16,23,38,56,72,91} and the search key/element is 23.

Now we find the mid values and check if the mid element is equal to 23. In the given array the mid value is 4 and the element at that position is 16 which is not equal to 23 so we compare 23 with 16 and it is greater so we move to the right side and repeat the process.

The next mid value is 56 which is greater than 23 so we move to the left side.

The mid value is 23 which is equal to the search element so the search is successful. We return the position of 23.

Now that we understood the algorithm completely let’s move to the coding part.

See also  INSERTION SORT ALGORITHM

Iterative Implementation of Binary Search

Python

# Binary Search in python


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

    # Repeat until the pointers low and high meet each other
    while low <= high:

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

        if array[mid] == x:
            return mid

        elif array[mid] < x:
            low = mid + 1

        else:
            high = mid - 1

    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) {

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

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

Run the above codes and observe the output.

See also  Linear Search in DSA

That’s it for this article. In the next article, we are going to have a look at Recursive implementation of binary search and the time complexity analysis.

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.