Binary search is a popular algorithm widely known for its efficiency and simplicity.
If you have had the joy to use it, I am sure you will have found that there are some important implementation differences, often referred to as variants.
In this article, I aim to describe some of them and what type of problems they solve.
In this article, I will refer “search space” as the list of items that might be visited during the search.
Given the array [1,2,3,4,5,6], I will assume there might be different types of search spaces:
- the search space [1, 2, 3] could mean visiting 1, 2 or 3
- the search space [3, 4, 5) could mean visiting 3, 4
- the search space (2, 3, 4, 5] could mean visiting 3, 4, 5
- the search space (2, 3, 4, 5) could mean visiting 3 or 4
Searching an element
The classic version of the algorithm is about searching an item in a sorted array that contains no duplicates.
Given [10, 30, 35, 43, 56, 67, 89, 90, 93, 99] find the index of 35, or return -1 if it doesn’t exist.
The classic algorithm would follow these iterations:
- [10,30,35,43,56,67,89,90,93,99], 56 > 35
- [10,30,35,43], 30 < 35
- [35,43], 35 == 35
Finding the smallest item that is greater than
A variation of the problem above may require finding the smallest item that is greater than a number.
A popular option is reusing the same visiting pattern as in the classic algorithm and only adding a variable to keep track of the lowest item found.