Binary Search

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

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;
Code language: C++ (cpp)
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

Time Complexity
Worst CaseO(log n)
Best CaseO(1)
Average CaseO(log n)
Space Complexity
Worst CaseO(n)

Applications

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

Linear Search

Here, We discuss about Linear Search, their implementation in C, time and space complexity and its applications. What is Linear Search? Linear Search is the simplest …
Read More

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to [email protected]. See your articles on the main page and help other coders.

Leave a Comment

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