Binary Search

Last updated on September 4th, 2023 at 09:41 pm

Here, We discuss about Binary Search, their implementation in C, time and space complexity and its applications.

What is Binary Search?

Binary Search is the most popular searching algorithm. It is efficient and most commonly used to solve problems.

The algorithm based on the idea that finding an element’s position in a sorted array.

Binary search works only on a sorted array. To use binary search, the array must be sorted first.

Binary Search Algorithm can be implemented in two ways are:

1. Iterative Method
2. Recursive Method

Implementation

Sample Code in C:

//Binary Search in C
#include<stdio.h>
int binarysearch(int arr[], 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(arr[mid] == x)
      return mid;
    if(arr[mid] < x)
      return mid + 1;
    else
      high = mid - 1;
  }
  return -1;
}
int main(void)
{
  int data[] = {3, 15, 8, 1, 38, -2, 7};
  int n = sizeof(data) / sizeof(data[0]);
  int x = 3;
  int result = binarysearch(data, x, 0, n-1);
  if(result == -1)
    printf("Element not found");
  else
    printf("Elements is found");
  return 0;

Output:
Element is found

Advantages

1. Efficient on very big list.
2. Can be implemented iteratively/recursively.

Disadvantages

1. Interacts poorly with the memory hierarchy (more cache miss).
2. Requires given list to be sorted.
3. Due to random access of list element, needs arrays instead of linked list.

Time and Space Complexity

Applications

1. Number guessing game
2. Word lists/ search dictionary etc

Related:

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎