How to logically interpret any variation of binary search

Question

It seems like there are eight variants of binary search (given a sorted list in ascending order):

1. Largest number less than target (but leftmost of duplicates)

2. Largest number less than target (but rightmost of duplicates)

3. Largest number less than or equal to target (but leftmost of duplicates)

4. Largest number less than or equal to target (but rightmost of duplicates)

5. Smallest number greater than target (but leftmost of duplicates)

6. Smallest number greater than target (but rightmost of duplicates)

7. Smallest number greater than or equal to target (but leftmost of duplicates)

8. Smallest number greater than or equal to target (but rightmost of duplicates)

How do I know how to correctly and logically set up the correct type of binary search for these? Every time I try, it seems like the logic tends to fail when lists get really small or when weird edge cases show up, which makes me think that I am going about the logic incorrectly.

Is there a better way to think about this kind of problem logically so that binary search can be set up better?

You always hear about how a high percentage of programmers can't code binary search correctly but then I'm not at all surprised to find that there's no exhaustive literature on how to correctly set up these 8 cases.

Answer 1

The mental model I use for binary search is the following: Let's assume we have a monotonically increasing function f: [a, b] -> {0,1} and we want to find the smallest number i from [a, b] with f(i) = 1, or b if no such number exists. The following algorithm will compute that result:

lo = a, hi = b
while lo < hi:
    # invariant: lo <= i <= hi
    mid = (lo + hi)/2  # or lo + (hi - lo) / 2 to avoid overflows
    if f(mid): 
        hi = mid
    else: 
        lo = mid + 1

In the end, lo = hi = i.

Interestingly, this code will never examine f(b), so it's fine if f is only defined on [a,b-1]. If f(b-1) = 0, then the code will report b as the answer. You can cover all the cases you mentioned using this, by just using the correct function f. For example:

(7) Smallest number greater than or equal to target (but leftmost of duplicates)

Let's say you have an array of size n.

Use a = 0, b = n, f(i) = array[i] >= target

(1) Largest number less than target (but rightmost of duplicates)

Use a = -1, b = n - 1, f(i) = (array[i+1] >= target).

Or alternatively, use solution for (7) and subtract 1. It should be clear that we just shifted everything by 1 here.

(2) Largest number less than target (but leftmost of duplicates)

This requires two searches if I'm not mistaken. You can use the solution for case (1) (say index i) and then use a = 0, b = i, f(j) = array[j] == array[i] to find the leftmost duplicate.

etc.

I don't think I ever made a mistake with binary search since I've started using this pattern.