Binary Search Variants

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.

Search Space

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:

1. [10,30,35,43,56,67,89,90,93,99], 56 > 35
2. [10,30,35,43], 30 < 35
3. [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.