Python Binary Search Template
Binary search runs in O(log n) over any sorted array, but the off-by-one variations bite everyone. This entry ships three runnable templates: the equality search, the lower-bound (`bisect_left`) variant, and the upper-bound (`bisect_right`) variant. Each one handles every edge case the test list throws at it.
1,085 views
33
def binary_search(nums, target):
"""Return the index of `target` in sorted `nums`, or -1 if absent."""
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
# Happy path.
print(binary_search([1, 3, 5, 7, 9, 11, 13], 7)) # 3
# Edges that catch off-by-one bugs.
print(binary_search([1, 3, 5, 7, 9, 11, 13], 1)) # 0 (first element)
print(binary_search([1, 3, 5, 7, 9, 11, 13], 13)) # 6 (last element)
print(binary_search([1, 3, 5, 7, 9, 11, 13], 4)) # -1 (between elements)
print(binary_search([1, 3, 5, 7, 9, 11, 13], 0)) # -1 (below range)
print(binary_search([1, 3, 5, 7, 9, 11, 13], 99)) # -1 (above range)
print(binary_search([], 5)) # -1 (empty array)
print(binary_search([42], 42)) # 0 (single element hit)
print(binary_search([42], 7)) # -1 (single element miss)The template uses a closed interval [lo, hi]. lo <= hi is the loop condition because the interval is inclusive on both ends, and lo = mid + 1 / hi = mid - 1 shrink it without ever revisiting mid. Computing mid = (lo + hi) // 2 is safe in Python (ints are unbounded), so you do not need the lo + (hi - lo) // 2 trick that C and Java need. Test against empty arrays, single-element arrays, the first and last elements, and out-of-range values: every binary-search bug shows up there.
def lower_bound(nums, target):
"""Index of the first item >= target. Equals len(nums) if target > all items."""
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
nums = [1, 2, 4, 4, 4, 5, 8]
print(lower_bound(nums, 4)) # 2 (first 4)
print(lower_bound(nums, 3)) # 2 (insert 3 here to keep sorted)
print(lower_bound(nums, 0)) # 0 (smaller than everything)
print(lower_bound(nums, 9)) # 7 (larger than everything: == len)
# Same answer from the standard library.
import bisect
print(bisect.bisect_left(nums, 4)) # 2
print(bisect.bisect_left(nums, 3)) # 2The lower-bound template uses the half-open interval [lo, hi). The condition flips to lo < hi and hi = mid (no -1) because hi is exclusive. The function returns the first index where nums[i] >= target, equivalently the leftmost spot you could insert target and stay sorted. For absent target, this is exactly the result you want: where it would go. bisect.bisect_left from the standard library is the same thing, so reach for the import in production code and use the template only when you need a custom comparator.
import bisect
def upper_bound(nums, target):
"""Index of the first item > target. Equivalent to bisect_right."""
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
nums = [1, 2, 4, 4, 4, 5, 8]
print(upper_bound(nums, 4)) # 5 (just past the last 4)
print(bisect.bisect_right(nums, 4)) # 5 (same answer from stdlib)
# Count of items equal to a target = bisect_right - bisect_left.
def count_equal(nums, target):
return bisect.bisect_right(nums, target) - bisect.bisect_left(nums, target)
print(count_equal(nums, 4)) # 3
print(count_equal(nums, 5)) # 1
print(count_equal(nums, 9)) # 0The upper bound is the left edge of 'strictly greater' and equals the right edge of 'equal'. The only line that changes from the lower-bound template is < becoming <=. Subtracting bisect_left from bisect_right gives the exact count of items equal to a target in O(log n), which is the canonical 'count occurrences in a sorted array' answer and the classic interview follow-up to plain binary search. For absent targets, both bisects return the same index and count_equal correctly returns 0.