Binary search is a five-line algorithm that developers still get wrong under interview pressure — off-by-one errors and infinite loops are the two most common bugs in all of interview coding. Learn one correct template, understand why each line is there, and you’ll never second-guess it again.

What you’ll learn

• The canonical, bug-free binary search template — lo <= hilo <= hi vs lo < hilo < hi, and when to use each.
• The overflow-free midmid habit: mid = lo + (hi - lo) // 2mid = lo + (hi - lo) // 2.
• lower_boundlower_bound / upper_boundupper_bound, hand-rolled and via Python’s bisectbisect module.
• Binary search on the answer — searching a range of possible answers instead of an array.
• Why binary search is $O(\log n)$, and the classic ways it breaks.

The canonical template: does the target exist?

The most common shape: search a sorted array for an exact value, return its index or -1-1. Search space is inclusive on both ends, so the loop keeps going while lo <= hilo <= hi — the space is empty exactly when lolo crosses past hihi.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2   # overflow-free habit -- see note below
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1            # target is to the right -- discard mid and everything left
        else:
            hi = mid - 1            # target is to the left -- discard mid and everything right
 
    return -1
 
 
arr = [1, 3, 4, 7, 9, 11, 13, 18, 21, 25]
print(binary_search(arr, 13))   # expect 6
print(binary_search(arr, 6))    # expect -1 -- not present

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2   # overflow-free habit -- see note below
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1            # target is to the right -- discard mid and everything left
        else:
            hi = mid - 1            # target is to the left -- discard mid and everything right
 
    return -1
 
 
arr = [1, 3, 4, 7, 9, 11, 13, 18, 21, 25]
print(binary_search(arr, 13))   # expect 6
print(binary_search(arr, 6))    # expect -1 -- not present

Watch lolo, midmid, hihi narrow the search space

lo <= hilo <= hi vs lo < hilo < hi: two templates, two purposes

There isn’t one “correct” binary search loop condition — there are two common templates, each suited to a different question:

The lo < hilo < hi template converges until lo == hilo == hi, landing exactly on the boundary you’re looking for — which is exactly what lower_boundlower_bound and upper_boundupper_bound need.

lower_boundlower_bound / upper_boundupper_bound, hand-rolled

lower_bound(arr, target)lower_bound(arr, target) finds the first index where arr[i] >= targetarr[i] >= target. upper_bound(arr, target)upper_bound(arr, target) finds the first index where arr[i] > targetarr[i] > target. Together they bracket every occurrence of targettarget in a sorted array.

def lower_bound(arr, target):
    lo, hi = 0, len(arr)   # hi is EXCLUSIVE here -- "one past the end"
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
 
def upper_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
 
arr = [1, 3, 3, 3, 5, 7, 9]
print("lower_bound(3):", lower_bound(arr, 3))   # first 3 -> index 1
print("upper_bound(3):", upper_bound(arr, 3))   # first index after all 3s -> index 4
print("count of 3s:   ", upper_bound(arr, 3) - lower_bound(arr, 3))

def lower_bound(arr, target):
    lo, hi = 0, len(arr)   # hi is EXCLUSIVE here -- "one past the end"
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
 
def upper_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
 
arr = [1, 3, 3, 3, 5, 7, 9]
print("lower_bound(3):", lower_bound(arr, 3))   # first 3 -> index 1
print("upper_bound(3):", upper_bound(arr, 3))   # first index after all 3s -> index 4
print("count of 3s:   ", upper_bound(arr, 3) - lower_bound(arr, 3))

lower_boundlower_bound / upper_boundupper_bound via bisectbisect

The standard library already implements exactly this, in C, via the bisectbisect module — no need to hand-roll it in production code.

import bisect
 
arr = [1, 3, 3, 3, 5, 7, 9]
 
print("bisect_left(3): ", bisect.bisect_left(arr, 3))    # same as hand-rolled lower_bound
print("bisect_right(3):", bisect.bisect_right(arr, 3))   # same as hand-rolled upper_bound
 
# insort keeps a list sorted after inserting -- finds the spot in O(log n),
# but the actual insertion still shifts elements, so it's O(n) overall
bisect.insort(arr, 4)
print("after insort(4):", arr)

import bisect
 
arr = [1, 3, 3, 3, 5, 7, 9]
 
print("bisect_left(3): ", bisect.bisect_left(arr, 3))    # same as hand-rolled lower_bound
print("bisect_right(3):", bisect.bisect_right(arr, 3))   # same as hand-rolled upper_bound
 
# insort keeps a list sorted after inserting -- finds the spot in O(log n),
# but the actual insertion still shifts elements, so it's O(n) overall
bisect.insort(arr, 4)
print("after insort(4):", arr)

Binary search on the answer

The pattern that turns binary search from “a way to search arrays” into “a way to solve optimization problems”: instead of searching an array, search the range of possible answers, using a feasibility check to decide which half to keep.

Koko Eating Bananas: Koko has pilespiles of bananas and hh hours. Each hour she picks one pile and eats up to speedspeed bananas from it (finishing a pile early doesn’t help — the rest of that hour is wasted). Find the minimum integer speedspeed that lets her finish every pile within hh hours.

The key insight: as speedspeed increases, the hours needed only ever decreases (or stays the same) — that monotonic relationship is exactly what binary search needs.

import math
 
def min_eating_speed(piles, h):
    def hours_needed(speed):
        return sum(math.ceil(pile / speed) for pile in piles)
 
    lo, hi = 1, max(piles)   # answer is somewhere in [1, max(piles)]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if hours_needed(mid) <= h:
            hi = mid          # speed=mid WORKS -- try to go slower (smaller)
        else:
            lo = mid + 1      # speed=mid too slow -- need to go faster (bigger)
    return lo
 
 
print(min_eating_speed([3, 6, 7, 11], 8))    # expect 4
print(min_eating_speed([30, 11, 23, 4, 20], 5))   # expect 30

import math
 
def min_eating_speed(piles, h):
    def hours_needed(speed):
        return sum(math.ceil(pile / speed) for pile in piles)
 
    lo, hi = 1, max(piles)   # answer is somewhere in [1, max(piles)]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if hours_needed(mid) <= h:
            hi = mid          # speed=mid WORKS -- try to go slower (smaller)
        else:
            lo = mid + 1      # speed=mid too slow -- need to go faster (bigger)
    return lo
 
 
print(min_eating_speed([3, 6, 7, 11], 8))    # expect 4
print(min_eating_speed([30, 11, 23, 4, 20], 5))   # expect 30

Every “minimize the maximum” or “maximize the minimum” phrasing — ship capacity over nn days, minimum time to complete tasks, splitting an array to minimize the largest subarray sum — reduces to this same shape: binary search over the answer, with an O(f(n))O(f(n)) feasibility check inside.

  graph TD
    A["Candidate speeds: 1 .. 11 (max pile)"] --> B["mid = 6 -> hours_needed(6) = 5 <= 8 -> feasible, try smaller"]
    B --> C["mid = 3 -> hours_needed(3) = 10 > 8 -> too slow, need bigger"]
    C --> D["mid = 4 -> hours_needed(4) = 8 <= 8 -> feasible, try smaller"]
    D --> E["lo == hi == 4 -> answer is 4"]

Time and space complexity

LeetCode problem set

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 704 — Binary Search · Easy

Problem. Given a sorted array of distinct integers and a targettarget, return its index, or -1-1 if absent. Must run in $O(\log n)$.

Constraints. 1 <= len(nums) <= 10^41 <= len(nums) <= 10^4, sorted ascending, all values distinct.

Examples. [-1,0,3,5,9,12], target = 9[-1,0,3,5,9,12], target = 9 gives 44 · target = 2target = 2 gives -1-1

LC 35 — Search Insert Position · Easy

Problem. Given a sorted array of distinct integers and a targettarget, return its index if found, otherwise the index where it would be inserted to keep the array sorted. Must be $O(\log n)$.

Constraints. 1 <= len(nums) <= 10^41 <= len(nums) <= 10^4, sorted ascending, distinct.

Examples. [1,3,5,6], target = 5[1,3,5,6], target = 5 gives 22 · target = 2target = 2 gives 11 · target = 7target = 7 gives 44 · target = 0target = 0 gives 00

LC 34 — Find First and Last Position of Element in Sorted Array · Medium

Problem. Given a sorted array, return the starting and ending index of a given targettarget, or [-1, -1][-1, -1] if it is absent. Must be $O(\log n)$.

Constraints. 0 <= len(nums) <= 10^50 <= len(nums) <= 10^5, sorted ascending, values may repeat.

Examples. [5,7,7,8,8,10], target = 8[5,7,7,8,8,10], target = 8 gives [3,4][3,4] · target = 6target = 6 gives [-1,-1][-1,-1] · [], target = 0[], target = 0 gives [-1,-1][-1,-1]

from bisect import bisect_left, bisect_right
lo = bisect_left(nums, target)
if lo == len(nums) or nums[lo] != target:
    return [-1, -1]
return [lo, bisect_right(nums, target) - 1]

from bisect import bisect_left, bisect_right
lo = bisect_left(nums, target)
if lo == len(nums) or nums[lo] != target:
    return [-1, -1]
return [lo, bisect_right(nums, target) - 1]

Recap

• One template, two flavors: lo <= hilo <= hi with inclusive bounds for exact matches; lo < hilo < hi with an exclusive hihi for boundary-finding (lower_boundlower_bound/upper_boundupper_bound).
• mid = lo + (hi - lo) // 2mid = lo + (hi - lo) // 2 is an overflow-free habit worth keeping even in Python, where integers never actually overflow.
• bisect.bisect_leftbisect.bisect_left / bisect.bisect_rightbisect.bisect_right are lower_boundlower_bound / upper_boundupper_bound, already written and tested in the standard library.
• Binary search on the answer: when a feasibility check’s result is monotonic in some parameter, binary search that parameter’s range instead of an array — turns many “minimize the maximum” problems into $O(f(n) \log(\text{range}))$.
• Off-by-one bugs and infinite loops almost always trace back to mixing bounds conventions — pick inclusive or exclusive hihi and stay consistent.

You’ve now covered sorting and searching, the two building blocks behind nearly every “optimize this over sorted or monotonic data” interview question.