Applications of Binary Search

In this article, we have listed and explained applications of Binary Search algorithm. The direct application is to search an element in logarithmic time but it can be applied in other problems in innovative ways.

The applications of Binary Search are:

  1. Find an element in a sorted array
  2. Applications of Binary Search beyond arrays
    2.1. To find if n is a square of an integer
    2.2. Find the first value greater than or equal to x in a given array of sorted integers
    2.3. Find the frequency of a given target value in an array of integers
    2.4. Find the peak of an array which increases and then decreases
    2.5. A sorted array is rotated n times. Search for a target value in the array.
  3. Real life applications of Binary Search
    3.1. Dictionary
    3.2. Debugging a linear piece of code
    3.3. Figuring out resource requirements for a large system
    3.4. Find values in sorted collection
    3.5. Semiconductor test programs
    3.6. Numerical solutions to an equation

We have explained each application in depth further in this article. Let us get started.

Introduction to Binary Search

Binary search is a searching algorithm more efficient than linear search. It is used to find the position of an element in the array only if the array is sorted. It works on the principle of divide and conquer ie the technique repeatedly divides the array into halves.

If the element is greater than the middle element, the left half is abondoned and the search continues in the right half. If the element is smaller than the middle element, the right half of the array is neglected and the search continues in the left half. The search stops when the subarray size reduces to zero.

Complexity

Best case time complexity: O(1)
Worst case time complexity: O(log n)
Average case time complexity: O(log n)
Space complexity: O(1)

Find an element in a sorted array

This is the most direct application of Binary Search.

It can be used to find an element in a sorted array in O(logN) time where N is the number of elements in the sorted array.

Applications of Binary Search beyond arrays

  1. To find if n is a square of an integer

We can perform binary search on the range [0,n]. At each step of the algorithm, we have the size of the remaining range or we already finish.

Implementation:

if(mid*mid==x):
  return mid
else if (mid*mid>x):
  binary_search(left,mid-1)
else:
  binary_search(mid+1,right)
  1. Find the first value greater than or equal to x in a given array of sorted integers.

(The main theorem)

Input:            x=4
                 a[]=2 | 3  |  5  | 6  |  7  |  8 | 10
How it works----      no | no | yes | yes| yes | yes| yes
Output:            5

The series of yes no nature represents the true false character of binary search to decide for a result.As a result, the first true is given out as the answer.

Implementation:

if(a[mid]>=target):
  ans=mid
  right=mid-1
else:
  left=mid+1
return ans

We keep overriding the value of ans of the basis of a better value which exists more towards the left since the array is already sorted. When a[mid] is still less than the target we move to the right part to fulfill the condition.If no value is greater than or equal to x we return a -1.Once when left>right,we return the ans.

More applications based on binary search

  1. Find the frequency of a given target value in an array of integers
  2. Find the peak of an array which increases and then decreases
  3. A sorted array is rotated n times. Search for a target value in the array.

Some real life applications of Binary Search

  1. Dictionary

A dictionary contains thousands of words. It's time consuming to go through and check for each word if we want to search "Voracious". We go to the middle page and compare the words on that page with "Voracious". If "Voracious" is alphabetically smaller than the word on the middle page then we can ignore all pages on the right side. If it is alphabetically larger than the word on the middle page then we ignore all pages on the left side. We keep repeating this process until we find the word.

  1. Debugging a linear piece of code

If a code has many steps mostly executed in a sequence and there's a bug, we can isolate the bug by finding the earliest step where the code produces results which are different from the expected ones.Ofcourse, it saves time.

  1. Figuring out resource requirements for a large system

Try running load tests on the system and binary search for the minimum amount of CPUs required to handle a predicted load.

  1. Any sorted collection from any language library like Java, .NET, C++ STL etc use binary search to find values. Hence the principles behind the implementations of the binary search should be known.

  2. Semiconductor test programs used for measuring digital timing or analog levels make extensive use of binary search.

  3. Binary search can be also used to find numerical solutions to an equation.

With this article at OpenGenus, you must have a strong idea of applications of Binary Search. Enjoy.