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 ruleofthumb 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 # startingcondition
right = len(array)  1
while lelft <= right: # loopcondition
mid = (left + right) / 2 # rangesplitting
if array[mid] == t: # loopshortcut
return mid
if array[m] < t: # rangeupdatecondition
left = mid + 1 # rangeupdatevalue
else:
right = mid  1
return 1 # loopending
 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 returnt
’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 arraysize 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 “howdoyouknow” 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 endofloop (before returning 1), what is the value ofleft
andright
? (e.g. would it point to the value below or higher thant
?)
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, n1]
is the typical and recommended for normal binary search because we would not have to worry about indexoutofrange.
There are also [0, n]
and [1, n1]
, 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:

whilelessthan (
left < right
orright  left > 0
) The loop will end with
left = right
(Unless the array is empty)
 The loop will end with

whilelessthanequal (
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.
 The loop will end with left pass over right (
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 recursivebased 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:

floorsplitting (
mid = (left + right) // 2
ormid = left + (right  left) / 2
) For this, remember that the mid can/will end up toucing or being equal to the left
left <= mid < right

ceilsplitting (
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.

movetomid (e.g.
left = mid
orright = mid
)  **movepassmid
 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 rulesofthumb are:

floorsplitting >
left
must movepassmid 
ceilsplitting >
right
must movepassmid
For example, in floorsplitting, there is a case when mid = left
. When that happened, if we left was movetomid, 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 ceilsplitting, 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 straightforward.
My rule of thumb is to pay attention to Range Update Condition and Range Update Value, especially, on what condition that we movepassmid. If we choose to movepassmid 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
t
s 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 thant
or return the initial right if every element is less thant
. 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
 If this is not expected outcome, we can add final check before the return.
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 tot
)
Thus, when the loop terminate at left = right
, we end up with:
 Everything before
left
is less thant
 The element at
right
element could bet
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)
returns0

find_first_less_than([0, 1, 2], t=0.5)
returns0
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, n1]
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 movetomid 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 movepassmid on the right side
return left
On the code above, please notice in the comment how I reason about moveto when mid 'could' still be the answer and movepass 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[right1:] 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 😃
Wanasit T
Clap to support the author, help others find it, and make your opinion count.