Binary Search

Binary search is also known as half-interval search or logarithmic search. It is a searching algorithm used to find the position of an element in the sorted array. The payoff for using a sorted array comes when we use a binary search. This kind of search is much faster than a linear search, especially for large arrays.

It uses the same approach you did when you were kid (if you were smart) and playing Number Guess game. In this game, a friend asks you to guess a number that he is thinking of between 1 and 10. When you guess a number, he tell you one of the three things i.e., whether your guess is larger than the number that he thinks, or its smaller or you guessed correctly.

If you were smart kid, to find the number in the fewest guesses, you should always start by guessing 5. If your friend says the number that you guessed is too high, then you assume the number is between 1 and 4. Then your next guess would be 2 (half way between 1 and 4). If he says too low, then your next guess would be 3 which is correct answer. Please refer the following table shows an example of a game session when the number to be guessed is 3.

Number Guess Game
Step Guessed NumberCorrect or NotPossible Range Values
01-10
15Too high1-4
22Too low2-4
33Correct

So the binary search compares the target element to the middle element of the array. If they are not equal, the half in which the target element cannot lie will be eliminated and the search will continue on the remaining half, again taking the middle element  of the remaining half to compare to the target element, and repeating this until the target element is found. If the search ends with the remaining half being empty, the target element is not in the array.

Binary Search Example

Time Complexity Analysis

In order to understand time complexity of binary search, please go through this sneppet How to calculate binary search complexity

So binary search runs in logarithmic time in the worst case you need to make O(log n) comparisons. where n is the number of elements in the array, the O is Big O notation, and log is the logarithm. Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search.

Space Complexity Analysis

Binary search takes constant O(1) space, meaning that the space taken by the algorithm is the same for any number of elements in the array.

A space complexity of O(1) means that the space required by this binary algorithm using iterative approach to process data is constant and it does not grow with the size of the data on which the algorithm is operating.

Conclusion

Binary search is faster than linear search (Please check Linear Search Time and Space Complexity Analysis) except for small arrays, but the array must be sorted first.

Leave a Reply

avatar
  Subscribe  
Notify of