Generalised Binary Search template

There are many implementations of binary search. While the general concept makes sense (find a mid point, then decide if you look at the left or the right, hence halving the search space), the specifics often confused me. Eg

• Do I need to worry about odd vs even length arrays?
• Is the mid point going to be exactly in the middle or slightly to the left of the middle?
• In the loop, will my left and right pointers ever cross?
• What happens when I exit my loop? Do I use the left pointer, or the right?

Then I found a nice explanation here. Below is my attempt to write it out in a clear way. This works for non empty arrays.

Motivating example here will be looking for a number in a given array.

First we start with initialising the left pointer (s for start) and right pointer (e for end). We make these point to actual spots in the array. So we have

s = 0
e = len(nums) - 1

I like this approach since we know that s and e always point to a spot in the array which actually holds a value (as opposed to algorithms where the pointers could fall off the end of the array or start at index -1 before the first element).

After that we write the algorithm. The few key points to note are that the mid idx m can take values equal to s, s+1, …, e-1 which means m+1 is always going to be in the array too.

s = 0
e = len(nums) - 1

while s < e: # note the strict less than    
    m = s + (e - s) // 2 
    # writing as s + (e - s) helps prevent overflow. We see m can be s, s+1, ..., e-1
    if nums[m] < target: # target strictly to the right of m and s < e strict inequality means the index m+1 is still in the array
        s = m + 1 # note s is strictly incremented since m >= s
    else:
        e = m # note e is strictly decremented since m < e
    # so after one loop, either s strictly goes up or e strictly goes down so we get closer to breaching the condition s < e

# when the condition is breached, we have that s = e. Hence the only value that could = target is nums[s] (which is also nums[e])

return s

This algorithm just returns s which is the only candidate idx that could match our search. It might need an extra line of code to chec

nums[s] == target

But we omit that extra line here since in cases where you are finding an index to add an element to, writing the algorithm in this style helps.