Implementing and Debugging Binary Search

Almost every programmer knows binary search. It’s often one of the first things we learn in CS course. However, most of professional programmers don’t actually have concrete experience in implementing the binary search (compare to -- experience in implementing a login page) unless you are practicing for coding interviews or participating competitive programming.

In this article, I want to look into an implementation of binary search and its variances (e.g. finding upper or lower bound).

There are other articles out there on how to write binary search correctly. Most of them try to explain Loop Invariant through the problem definition and formal analysis. This article takes the opposite appoarch. It focuses on practical techniques, pitfalls, or rule-of-thumb learned from discussions with several programmers with various background (web developers, mobile developers, competitive programmer, …), which I hope a typical coder can quickly get it after reading this. There is only small theoritical reference at the end and no mathmetical proof.

Note: All code examples are written in Python and I also assume you have a basic knowledge of binary search.

A Binary Search’s Implementation

Let’s do a code review for a typical binary search. Please read the following binary search and answer the questions below.

def binary_search(array, t):

    left = 0		            # starting-condition
    right = len(array) - 1
    
    while lelft <= right:           # loop-condition
    
        mid = (left + right) / 2    # range-splitting
        
        if array[mid] == t:         # loop-shortcut
            return mid
        
        if array[m] < t:            # range-update-condition
            left = mid + 1          # range-update-value
        else:                        
            right = mid - 1

    return -1                       # loop-ending

• Does this binary search will always stop (or it can stuck in an infinite loop)?
• Does this binary search work correctly (if there is t in the array it will definitely return t’s index, otherwise it will definitely return -1)?
• Or do you spot any bug....

Before reading on, I encourage spending a few minutes to read the code and answer the questions.

…

So, the implementation above works (if we don’t consider array-size and integer limitation). The answer is “yes” to both of the first two questions. The code above is actually copied right from the Wikipedia’s page. You can simply remember the exact code above if you simply need a binary search.

However, to master the binary search implementation, the rest of this article will try to explain not just if, but “why” or “how-do-you-know” if a binary search code works.

First, how do you know if the above function always end and does not stuck in an infinite loop? This often a common bug when implementing a binary search.

Second, how do you know if the code above always find t correctly? Additionally, if we want to look into binary search variances, we need to also think about these questions:

• If there are multiple t in the array, which one of them will be returned?
• If there is no t in the array, at the end-of-loop (before returning -1), what is the value of left and right? (e.g. would it point to the value below or higher than t?)

We will answer those questions just by reading, observing, and reasoning about the code (with causal common senses). Having testing cases or examples are important in practice, but we will not rely on that.

Binary Search’s Parts

To understand and reason the binary search, we need to break the implementation into different parts. For each part, we analyst its the implementation choices and their effects in combination.

Note: these are the terminology I came up with to have precise references.

Starting Condition

This is where we initialize the left and right. The often ignored assumption here is that the initial range must include all possible answer.

The [0, n-1] is the typical and recommended for normal binary search because we would not have to worry about index-out-of-range.

There are also [0, n] and [-1, n-1], which are useful for upper or lower bound detection variants, but we may have to pay extract attention in Range Splitting.

Loop's Condition

There are two subtlely different conditions I see people use. Etiher of them works, however, the post condition (or what left and right will be at the end) are pretty different:

• while-less-than (left < right or right - left > 0)

  • The loop will end with left = right (Unless the array is empty)

• while-less-than-equal (left <= right)

  • The loop will end with left pass over right (left = right + 1)
  • It often use with Loop’s Shortcut because the left = right case will still be in the loop and we don’t need anther check at the end.

Note: There are also clever implementations that just stop the loop early when the range get narrow (e.g. while right - left > 1 or often recursive-based implementations) to avoid handling edge cases all together. However, I will ignore those cases in this article.

Loop’s Shortcut

This is when we check if the mid element is exactly equal to the t and, then, terminate the loop or function. If the array contains t, the loop often ends here. Having the shortcut could improve the search performance, esp. when there are a lot of duplicate target elements and we just find any of them.

The downside of the shortcut is it make ending condition less predictable and we cannot rely on the shortcut to detect lower or upper bound if the value doesn’t exist in the array. (Personally, I like not having the shortcut.)

Range Splitting

There are also two subtlely different ways to pick middle index integer. Each choice here has pretty profound effect:

• floor-splitting (mid = (left + right) // 2 or mid = left + (right - left) / 2)

  • For this, remember that the mid can/will end up toucing or being equal to the left
  • left <= mid < right

• ceil-splitting (mid = (left + right + 1) // 2)

  • For this, remember that the mid can/will end up toucing or being equal to the right
  • left < mid <= right

Range Update Condition

If we have have Loop's Shortcut, we do not have to pay more attention on how to handle array[mid] == t case.

However, if we don’t have the shortcut (or if we care about getting correct upper or lower bound), we need to pay attention on whether to move left or right in array[mid] == t case.

Range Update Value

This is where we decide how far we want to update left and right. Again, there are two subtlely different choices with profound effect.

• move-to-mid (e.g. left = mid or right = mid)
• **move-pass-mid
  • e.g. l = m + 1 or r = m -1

Loop’s Ending

In many cases, we need to have the final check after the loop (e.g. return left if array[left] == t else -1). However, there is nothing special about this. Most of important coding decisions happened inside the loop.

How to ensure the termination

To ensure binary search termination, make sure the mid (and so left or right) change on every iteration.

If we can reason or determine that mid value will always change, we can be 100% confidence that the binary search will not be struck in the infinite loop. It will end (but, whether the output is correct or not, is in the next section).

This can be done by paying attention to Range Splitting and Range Update Value. My suggested rules-of-thumb are:

• floor-splitting -> left must move-pass-mid
• ceil-splitting -> right must move-pass-mid

For example, in floor-splitting, there is a case when mid = left. When that happened, if we left was move-to-mid, the mid and left can keep staying at the same value.

while left <= right:                
    mid = (left + right) // 2            
    ...

    if array[mid] < t:    # Stuck in an infinite loop 
        left = mid        # when `left = mid` and `array[mid] < t`
    else:
        right = mid - 1

Comparing to:

while left <= right:                
    mid = (left + right) // 2            
    ...

    if array[mid] < t:  
        left = mid + 1    # The next left will pass mid, thus, not repeat
    else:
        right = mid

Or, comparing to:

while left <= right:                
    mid = (left + right + 1) // 2   # In ceil-splitting, mid would always be more than left (left = mid never happen)
    ...


    if array[mid] < t:          # Then, this is fine. 
        left = mid              # The next mid will be more than current left and mid.
    else:
        right = mid - 1         # However, we have to be careful on the right instead

How to ensure the correct answer

To ensure binary search correct answer, make sure any potential answer is kept between left and right on every iteration.

Or do not move the left or right pass the element we are looking for. But, remember, we also need to do that while making sure left and right keep changing to terminate the loop (see. previous section).

In most case, the element we are looking for is t, however, it can also be something else (e.g. the first element less than or equal to t). Understanding what's actually being kept between left and right and determine the final outcome is possible, but not always straight-forward.

My rule of thumb is to pay attention to Range Update Condition and Range Update Value, especially, on what condition that we move-pass-mid. If we choose to move-pass-mid when mid is or could potentially be the answer, then the result could be incorrect.

For example:

left, right = 0, len(array) - 1

while left < right:                
    mid = (left + right) // 2

    if array[mid] < t:  
        left = mid + 1              
    else:                 # This is a bug.
        right = mid - 1  # When array[mid] == t, we will move pass the answer

return left

The more correct implementation would be:

left, right = 0, len(array)

while left < right:                
    mid = (left + right) // 2
  
    if array[mid] < t:     
        left = mid + 1     # Move `pass` any element less than `t`         
    else:
        right = mid        # But move `to` (not pass) an element more than or equal to `t`

return left                # Need final check?

Now, if t is in the array, the implementation above will not skip and find it.

However, also notice that:

• If there are multiple ts in the array, it will find the first or left most one.
• If t is not in the array, it will find the first value larger than t or return the initial right if every element is less than t.
  • If this is not expected outcome, we can add final check before the return. return left if left < len(array) and array[left] == t else -1

In summary, the code above returns the first element with value more than equal to t.

This can be inferred from two conditions in the loop:

• We skip pass everything that less than t
• We keep (move to, not move pass) an element more than or equal to t (until we find another element closer to t)

Thus, when the loop terminate at left = right, we end up with:

• Everything before left is less than t
• The element at right element could be t or more.
  ...

Let’s see another example. This time let’s tweak the binary search to find the first element that less than t, or find_first_less_than.

• find_first_less_than([0, 1, 2], t=1) returns 0
• find_first_less_than([0, 1, 2], t=0.5) returns 0

def find_first_less_than(array, t):

    left = -1                # If everything is more than `t`, lets return -1
    right = len(array) - 1   # Thus, initial range [-1, n-1]

    while left < right:
        mid = (left + right + 1) // 2 # To ensure loop termination, use ceil split here 

        if array[mid] < t:   # `mid` could be the first less than `t` element (unless we find something else),
            left = mid       # so we are going move-to-mid and keep it 
        
        else:                # If `mid` is equal or more than `t`, it is not the one we are looking for,
            right = mid - 1  # so we can safely move-pass-mid on the right side

    return left

On the code above, please notice in the comment how I reason about move-to when mid 'could' still be the answer and move-pass if it is 'definately not' the answer.

Theoritical Reference

So far, we have been talking about the practical tips and pitfalls. In this section, I want to generalize the suggestions and related them to CS theories. For a longer version, there is also a series of articles from Mike Taylor that explains how to use mathematical tools to write correct binary search. However, I will try to explain that with our examples in fewer paragraphs.

If you could remember only a few things from this article, I wish those are the two rules of thumb to ensure termination and correctness we talked about:

• The value of mid (and so left or right) must change on every iteration.
• The potentially correct element(s) must be kept between left and right on every iteration

The first rule is related Loop Variant (or Bound Function). It's a theoritical upper bound for the number of iterations. In binary search, the bound is [right - left] or the searching range’s size. If this bound is strictly decreasing, the function will terminate.

The second factor is Loop Invariant. The invariants are properties that remain unchanged on every iteration. In this case, having the target element between left and right is the invariant, or to be precise:

• Invariant #1: all values in array[:left] are less than t (or the element we are looking for)
• Invariant #2: all values in array[right-1:] are more than t (or the element we are looking for)

If our code update left and right in the way that doesn’t break those two promises, when the function is terminated, we are guaranteed to reach the desired state.

Final Thought

At the end of the day, writing a correct binary search is hard because we don’t practice.

Many of the programmer colleagues I asked, couldn’t write it on the spot. For those who can, many of them admittedly did not feel any confident if their code were correct, let alone thinking about Loop Invariant or mathematical guarantee.

In a month from now, I'd probably forget all about how it all works myself. (I’d also not be surprise if someone found a bug in the example code. Please let me know)

However, that's probably I want to share this interesting experience (how people around me write binary search and how their reason about it correctness) before leaving for holiday. If you read to this paragraph, I hope you find it interesting too 😃