Fearless Binary Search
Oct 7, 2020 · 1025 words · 5 minutes read
I find it’s hard to write bug free binary search code when solving problems in Leetcode. This post try to make it easier.
Basic Version
Problem: (Leetcode 704)
Given a nonempty sorted integer array, find target number and return its index.
Example:
Input: nums = [1,0,3,5,9,12], target = 9
Output: 4 (because 9 exists in nums and its index is 4)
Input: nums = [1,0,3,5,9,12], target = 2
Output: 1 (2 does not exist in nums so return 1)
Solution:


It’s easy. Attentions and explanation:
 Initialize low and high pointers to
0
andlen(nums)1
, which are inclusive.  Loop condition is
lo <= hi
. Why it is<=
? Try a simple test casenums=[1], target=1
and you can find the reason.  Line6 using
mid = lo + (hi  lo) // 2
just to avoid integer overflow instead of usingmid = (lo + hi) // 2
.  Line10 using
lo = mid + 1
because whennums[mid] < target
target must be in range[mid+1, hi] (inclusive)
, so we can safely movelo
to skipmid
and make itmid + 1
. Similar at Line11 forhi
.
Find First
Problem:
Given a integer array sorted in ascending order, find the index of the first number larger than target.
Example:
Input: nums = [1,3,5,7,9], target = 6
Output: 3 (because 7 is the first number larger than target and its index is 3)
Input: nums = [1,3,5,7,9], target = 9
Output: 1 (because no one larger than target)
Solution:


This problem is to find the first item that meet certain requirement.
1 3 5 7 9 (find first num > target 6)
F F F T T (F is False meaning num <= target; T is True)
^
You may use above example to verify the code.
Explanation:
 Loop condition is
lo < hi
, it means when loop is ended we expectlo == hi
, andlo
is the result we are looking for.  Line7&8,
num[mid] > target
is when meeting the requirement, we need to dohi = mid
. Why only tomid
? consider following example1 3 5 7 9 (find first num > target 2) F T T T T ^
in first loop run, mid is 2, nums[mid] is 5 which meet the requirement. We know every number after
mid
will also be True so the result is on the first half and we need to movehi
. We don’t know if 5 is the first True, so we can only movehi
tomid
. (We can’t movehi
tomid1
since it will miss the result if 5 is the first True.)  Line9&10, when
mid
not meeting the requirement, we are safe to movelo
tomid+1
because we know mid is not the result.  After loop, the result we are looking for is the
lo
(it is equal tohi
given our loop condition).  But we need exception check, as line12. If the result we find still doesn’t meet the requirement, we return exception. consider this following example
1 3 5 7 9 (find first num > target 9) F F F F F ^
eventually
lo
is 5, but still doesn’t meet the requirement, so we return 1.
Find Last
Problem:
Given a integer array sorted in ascending order, find the index of the last number smaller than target.
Example:
Input: nums = [1,3,5,7,9], target = 6
Output: 2 (because 5 is the last number smaller than target and its index is 2)
Input: nums = [1,3,5,7,9], target = 1
Output: 1 (because no one smaller than target)
Solution:


This problem is to find the last item that meet certain requirement.
1 3 5 7 9 (find last num < target 6)
T T T F F
^
You may use above example to verify the code.
Explanation:
 Why line6 is different from the code in “find first” section? To avoid dead loop. Consider following example:
1 3 (find last num < target 2) T F
without the
+1
it will loop forever. So always remember to verify your code with this 2 items test case (or you can try to remember the special handling for “find last”).  Now when meeting requirement, we know the result is in the second half and we need to move
lo
. We don’t know ifmid
is the last one that meets requirement, so we move only movelo
tomid
.  Similar handling for
hi
and exception as “find first”.
Summary
There are many patterns/templates to correctly implement binary search. This post introduces the one I like best.
The high level structure is simple: just two points plus a while loop. We need to pay attention to the while loop condition and how to move pointers in different cases. At last, don’t forget to check edge cases.
More Exercise:
 Leetcode 34. Find First and Last Position of Element in Sorted Array
Sample solution: gist  Leetcode 74. Search a 2D Matrix
Sample solution: gist
Reference: