Modified Binary Search: Introduction

About the pattern  

The modified binary search pattern is an extension of the traditional binary search algorithm and can be applied to a wide range of problems. Before we delve into the modified version, let’s first recap the classic binary search algorithm.

Classic Binary Search

Binary search is an efficient search algorithm for searching a target value in sorted arrays or sorted lists that support direct addressing (also known as random access). It follows a divide-and-conquer approach, significantly reducing the search space with each iteration. The algorithm uses three indexes—start, end, and middle—and proceeds as follows:

1. Set the start and end indexes to the first and last elements of the array, respectively.

2. Calculate the position of the middle index by taking the average of the start and end indexes. For example, if $start=0$ and $end=7$, then $middle= \lfloor (0+7)/2 \rfloor = 3$.

3. Compare the target value with the element at the middle index.

4. If the target value is equal to the middle index element, we have found the target, and the search terminates.

5. If the target value is less than the middle index element, update the end index to $middle - 1$ and repeat from step $2$ onwards. Because the array is sorted, all the values between the middle and the end indexes will also be greater than the target value. Therefore, there’s no reason to consider that half of the search space.

6. If the target value is greater than the middle index element, update the start index to $middle + 1$ and repeat from step $2$. Again, because the array is sorted, all the values between the start and the middle indexes will also be less than the target value. Therefore, there’s no reason to consider that half of the search space.

7. Continue the process until the target value is found or if the search space is exhausted, that is, if the start index has crossed the end index. This means that the algorithm has explored all possible values, which implies that the search space is now empty and the target value is not present.

Note: We’re assuming the array is sorted in ascending order. If it’s sorted in descending order, we’ll do the opposite when changing the positions of the start and end pointers. Also, to avoid integer overflow when calculating the middle index, especially in languages with limited integer ranges, we can use start + (end - start) / 2 instead of (start + end) / 2.

The following illustration shows how a binary search operation works using the techniques described above: