Binary search algorithm and usage

 

A binary search algorithm finds the position of a specified value within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found then its position, is returned. If the key is less than the middle element, then the algorithm repeats on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special “Not found” indication is returned.

The binary search algorithm is the fastest algorithm to find the element in sorted array.

  • Worst case performance: O(log2n)
  • Best case performance: O(1)

Practical examples of binary search algorithm:

  • Implementing a “switch() … case:” construct in a virtual machine where the case labels are individual integers. If there are 100 cases, the correct entry can be find in 6 to 7 steps using binary search, where as sequence of conditional branches takes on average 50 comparisons.
  • Doing fast substring lookup using suffix arrays, which contain all the suffixes of the set of searchable strings in lexiographic ordering.
  • Binary search algorithm is used in 3D games and applications. Space is divided into a tree structure and a binary search is used to retrieve which subdivisions to display according to a 3D position and camera.

Steps to implement binary search algorithm:

  1. Compare searchElement with the middle element of array.
  2. If searchElement matches with middle element, we return the mid index.
  3. Else If searchElement is greater than the mid element, then searchElement can only lie in right half subarray after the mid element. So we recur for right half.
  4. Else (searchElement is smaller) recur for the left half.

 

Leave a Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
Notify of