Binary Search Template and Variants

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 <= hi vs lo < hi, and when to use each.
• The overflow-free mid habit: mid = lo + (hi - lo) // 2.
• lower_bound / upper_bound, hand-rolled and via Python’s bisect 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 cue

You are looking at a binary search when…

• The array is sorted (or rotated-sorted) and you need a position or a membership test.
• The constraint says $n \le 10^5$ or more and the problem states $O(\log n)$ — that requirement is the hint.
• You need the first or last index satisfying a predicate: insertion point, first bad version, count of a value. That is lower_bound / upper_bound, not an exact search.
• The answer is a number in a known range and you can check a candidate faster than you can construct it — “minimise the maximum”, “maximise the minimum”. See binary search on the answer.
• You can answer “can I rule out one whole side?” at any probe — even without sortedness. Peak finding works on unsorted input for exactly this reason.

When it is the wrong tool. An unsorted array with no monotonic predicate: a hash set is $O(1)$ for membership and a linear scan is $O(n)$ for anything else — sorting first to enable binary search costs $O(n \log n)$ and is usually a loss for a single query. For many queries on static data, sort once and binary search repeatedly. And in Python, reach for bisect before hand-rolling: it is C-speed and correct, and the two functions are exactly lower_bound and upper_bound.

The canonical template: does the target exist?

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

binary_search_exact.py

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

Why lo + (hi - lo) // 2 instead of (lo + hi) // 2

Python integers have arbitrary precision, so (lo + hi) // 2 can never overflow here. In languages with fixed-width integers (C, Java, C++), if lo and hi are both near the max representable value, lo + hi can overflow before the division happens, producing a negative or wrapped mid. lo + (hi - lo) // 2 never adds two large numbers together, so it’s safe everywhere. Writing it this way in Python too is free insurance and a habit worth keeping.

Watch lo, mid, hi narrow the search space

sketch Binary search: lo, mid, hi narrowing on a sorted array p5.js Pause Restart

Each step computes mid halfway between lo and hi, compares arr[mid] to the target, then discards the half that can't contain it.

lo <= hi vs lo < 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:

Template	Bounds	Question it answers
while lo <= hi	lo, hi = 0, len(arr) - 1 (inclusive both ends)	“Does the target exist? Give me its index.”
while lo < hi	lo, hi = 0, len(arr) (hi is exclusive)	“Give me the boundary — first index satisfying some condition.”

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

lower_bound / upper_bound, hand-rolled

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

lower_upper_bound.py

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_bound / upper_bound via bisect

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

bisect_module.py

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)

Match your bounds to your loop condition

bisect_left/bisect_right (and the hand-rolled versions above) use hi = len(arr) — an exclusive upper bound — paired with while lo < hi. The exact-match template uses hi = len(arr) - 1 — inclusive — paired with while lo <= hi. Mixing the two conventions in one function is the single most common source of off-by-one bugs.

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 piles of bananas and h hours. Each hour she picks one pile and eats up to speed bananas from it (finishing a pile early doesn’t help — the rest of that hour is wasted). Find the minimum integer speed that lets her finish every pile within h hours.

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

koko_eating_bananas.py

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 n 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)) feasibility check inside.

diagram Binary search on the answer: narrowing the feasible speed mermaid

  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"]

Off-by-one and infinite loops — the two classic bugs

1. Wrong narrowing step. Writing lo = mid instead of lo = mid + 1 (or hi = mid instead of hi = mid - 1 in the inclusive template) can leave mid unchanged forever when lo and mid land on the same value — an infinite loop, not just a wrong answer.
2. Mismatched bounds and condition. Using hi = len(arr) (exclusive) with while lo <= hi under-searches by one, or over-indexes past the array’s end. Always pick one convention (inclusive-hi/lo <= hi, or exclusive-hi/lo < hi) and keep every line of the function consistent with it.

Dry run

The three templates on [1, 2, 2, 2, 5, 8]

The array deliberately has a run of duplicates, because that is where the templates diverge.

Target	bs_exact	lower_bound	upper_bound	Count = upper - lower
2	2	1	4	3
3	-1	4	4	0
0	-1	0	0	0
9	-1	6	6	0

Verified against bisect.bisect_left and bisect.bisect_right — identical at every row.

Four things this settles:

• bs_exact returns an index, not the first. For target 2 it returns 2, which is neither the first (1) nor the last (3) occurrence — just wherever the halving happened to land. If a problem asks for the first or last occurrence, the exact-search template is the wrong one and no amount of tweaking the comparisons fixes it.
• upper_bound - lower_bound is the count, here 3 for the three 2s. That is the standard way to count occurrences in $O(\log n)$, and it is why both variants exist.
• A missing value still returns a meaningful position. Target 3 gives 4 from both bounds — the index where 3 would be inserted. So lower_bound doubles as “insertion point”, which is LC 35 in its entirety.
• Out-of-range targets return the ends, not -1. Target 0 gives 0; target 9 gives 6, which is len(a) — one past the end, and a legal insertion point rather than an error. Note hi starts at len(a), not len(a) - 1, in the bound templates precisely so that 6 is reachable.

The two loop shapes, side by side

	Exact search	Boundary search
Init	lo, hi = 0, len(a) - 1	lo, hi = 0, len(a)
Loop	while lo <= hi	while lo < hi
Move	lo = mid + 1 / hi = mid - 1	lo = mid + 1 / hi = mid
Return	inside the loop, else -1	lo, after the loop

hi = mid versus hi = mid - 1 is the whole distinction. In an exact search you have already proved a[mid] != target before moving, so mid can be discarded. In a boundary search mid is a live candidate for the answer until something better is found, so it must stay in the window.

The two mismatches are the source of nearly every binary-search bug:

• while lo < hi with hi = mid - 1 skips the answer — it discards a candidate it never disproved.
• while lo <= hi with hi = mid hangs forever — when lo == hi, mid == lo, and hi = mid changes nothing.

Termination for the boundary shape: lo < hi guarantees mid < hi under floor division, so hi = mid strictly shrinks the window and lo = mid + 1 strictly grows lo. Every iteration makes progress, so it cannot loop.

Time and space complexity

Operation	Complexity
Binary search on a sorted array	$O(\log n)$
lower_bound / upper_bound (hand-rolled or bisect)	$O(\log n)$
Binary search on the answer (feasibility check costs $O(f(n))$)	$O(f(n) \log(\text{range}))$
Space	$O(1)$

The variant map

Variant	The template	Canonical problem
Does the target exist?	Exact search, lo <= hi, return inside	704
Insertion point	lower_bound — bisect_left	35 Search Insert Position
First and last occurrence	lower_bound and upper_bound - 1	34 Find First and Last Position
Count occurrences	upper_bound - lower_bound	34
First index satisfying a predicate	Boundary search on the predicate, not the value	278 First Bad Version
Rotated sorted array	Identify which half is sorted, then test the target against it	33 · 81 · details
Peak in an unsorted array	Boundary search on the local slope — no sortedness needed	162 · 852
Search a 2D matrix	Binary search the flattened index with divmod	74
Minimise the maximum / maximise the minimum	Binary search the answer, with a feasibility predicate	1011 · 410 · 875
kth smallest in a sorted matrix	Binary search the value, counting entries $\le x$	378
Real-valued answer	Fixed ~100 iterations, or until hi - lo < eps	644
Median of two sorted arrays	Binary search the split point of the shorter array	4

bisect is the stdlib version, and it is the same two functions

bisect.bisect_left(a, x) is lower_bound; bisect.bisect_right(a, x) is upper_bound. Verified identical on every row of the trace above. Both accept lo and hi to restrict the range, and insort_left / insort_right do the search plus the insertion.

Since Python 3.10 both take a key= argument, which removes the old trick of maintaining a parallel list of keys. Reach for these in real code and hand-roll only when the interviewer wants the mechanics — and say which one you would use, because knowing bisect_left from bisect_right is the actual skill being tested.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

6 problems

2 easy4 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○35Search Insert PositioneasyExactly `lower_bound`: the first index where the target could be inserted to keep the array sortedLeetCode Top Interview 150
• ○704Binary SearcheasyThe canonical exact-match template, direct applicationNeetCode 150
• ○33Search in Rotated Sorted ArraymediumThe exact-match template, with one extra check per step to figure out which half is still sortedNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftbloomberg
• ○875Koko Eating BananasmediumBinary search on the answer, as aboveNeetCode 150googleamazonbytedance
• ○34Find First and Last Position of Element in Sorted Arraymedium`lower_bound` and `upper_bound` back to backLeetCode Top Interview 150
• ○981Time Based Key-Value StoremediumNeetCode 150

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 target, return its index, or -1 if absent. Must run in $O(\log n)$.

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

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

pch.exerciseTag pch.exerciseTitle

Editorial

The canonical exact search. Each comparison halves the range.

Time $O(\log n)$. Space $O(1)$.

Getting the loop shape right is the whole content, and it is worth naming the two forms explicitly because mixing them is the most common binary-search bug:

• while lo <= hi with lo = mid + 1 / hi = mid - 1 — for finding an exact value. mid is fully excluded once tested, and the loop must consider the case lo == hi, hence <=.
• while lo < hi with hi = mid — for finding a boundary, where mid may itself be the answer and must stay in range.

([5], 5) and ([5], -5) are the single-element tests: with lo < hi the loop body would never run and the first would wrongly return -1.

(lo + hi) // 2 cannot overflow in Python. In C++ or Java you would write lo + (hi - lo) // 2, which is worth mentioning since it is the reason that idiom exists.

Follow-ups: “Where would it be inserted if absent (LC 35)?” — next problem, and it needs the boundary shape. “First and last occurrence with duplicates (LC 34)?” — two boundary searches. “Rotated array (LC 33)?” — see Binary Search on Rotated Arrays. “Use bisect?” — bisect_left does this; mention it, then write the loop.

LC 35 — Search Insert Position · Easy

Problem. Given a sorted array of distinct integers and a target, 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^4, sorted ascending, distinct.

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

pch.exerciseTag pch.exerciseTitle

Editorial

This is lower bound: the first index whose value is >= target. That single definition answers both cases — if the target is present, its own index is the first such position; if absent, that position is exactly where it belongs.

Time $O(\log n)$. Space $O(1)$.

Two changes from LC 704, both necessary:

• hi = len(nums), not len(nums) - 1. target = 7 must return 4, which is one past the last index. Starting hi at 3 makes that answer unreachable.
• hi = mid, never mid - 1. mid is a live candidate for the boundary.

The loop terminates with lo == hi, and that common value is the answer — which is why nothing is returned from inside the loop.

This is precisely bisect.bisect_left(nums, target). Knowing that the standard library already has both bisect_left (lower bound) and bisect_right (upper bound) is worth stating — and knowing which is which is what LC 34 tests.

Follow-ups: “First and last occurrence (LC 34)?” — next problem: bisect_left and bisect_right. “With duplicates, which index does this give?” — the leftmost. “How do you remember the two shapes?” — exact search excludes mid and needs <=; boundary search keeps mid and needs <.

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 target, or [-1, -1] if it is absent. Must be $O(\log n)$.

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

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

pch.exerciseTag pch.exerciseTitle

Editorial

Two boundary searches, differing by one comparison:

• Lower bound — first index with nums[i] >= target.
• Upper bound — first index with nums[i] > target. The last occurrence is one before it.

Time $O(\log n)$ — two logarithmic passes. Space $O(1)$.

The presence check is essential and easy to omit. The lower bound returns an insertion point whether or not the target exists, so you must verify both that it is in range (first == len(nums) guards the empty array and past-the-end cases) and that the value there is the target. ([], 0) and ([5,7,7,8,8,10], 6) both exercise it.

Once you recognise these as bisect_left and bisect_right, the whole problem is two library calls:

python

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]

Worth showing — it demonstrates you know the standard library — but interviewers usually want the hand-written version, since the point is the boundary logic.

([2,2], 2) giving [0,1] confirms the range spans all duplicates.

Follow-ups: “Count occurrences?” — upper - lower, no extra work. “Only the first occurrence?” — one search. “Why two searches and not one plus a scan?” — a linear scan over duplicates would be $O(n)$, which breaks the requirement.

Interview follow-ups

They ask	What they’re checking	The answer
“Find the first occurrence, not any occurrence”	Whether you know the templates differ	The exact-search template cannot do it — on [1,2,2,2,5,8] it returns index 2 for target 2, neither first nor last. Switch to lower_bound: while lo < hi with hi = mid
“Count how many times x appears, in $O(\log n)$”	Composing the two bounds	upper_bound(x) - lower_bound(x). Verified: 3 for the three 2s
“Why hi = mid and not hi = mid - 1?”	The core distinction	In an exact search you have proved a[mid] != target, so mid is discardable. In a boundary search mid is still a candidate, so discarding it skips the answer. Pairing lo <= hi with hi = mid instead hangs forever
“Prove your loop terminates”	Rigour	For lo < hi with floor division, mid < hi always — so hi = mid strictly shrinks the window and lo = mid + 1 strictly advances lo. Every iteration makes progress
“(lo + hi) // 2 can overflow”	Language awareness	Not in Python — integers are arbitrary precision. In C++ or Java use lo + (hi - lo) // 2. Knowing why the idiom exists beats copying it
“The array is not sorted. Can you still binary search?”	The real precondition	Sometimes — what is required is a monotonic predicate, not sortedness. Peak finding works on arbitrary input because “the surviving range contains a peak” is preserved at every step
“What if the target is out of range?”	Edge cases	lower_bound returns 0 or len(a), both legal insertion points — which is why hi starts at len(a), not len(a) - 1, in that template. Verified: 0 for target 0, and 6 for target 9
“Would you use bisect?”	Practical judgement	Yes, in real code — bisect_left is lower_bound and bisect_right is upper_bound, both in C, and since 3.10 both take key=. Then offer the hand-rolled version if the mechanics are the point
“Now the answer is a value, not an index”	Recognising the bigger pattern	Binary search on the answer: pick bounds that provably bracket it, write a monotonic feasible(mid), narrow with the boundary template. $O(n \log R)$ over the value range, not $O(n \log n)$
“How many iterations for $n = 10^9$?”	Sanity with numbers	About 30, since $2^{30} \approx 10^9$. Useful for arguing that a $O(n \log R)$ solution fits when a linear scan over the value range would not

Self-check

pch.quizTag pch.quizDefaultTitle

1. On [1,2,2,2,5,8], the exact-search template returns 2 for target 2. What is wrong with using it to find the first occurrence?

   A Nothing -- index 2 is the first occurrence B Index 2 is neither the first (1) nor the last (3) -- it is just where the halving landed. Finding the first requires the lower_bound template C The array must be deduplicated first D It should return -1 when duplicates exist
   pch.quizShowAnswer

   B — Index 2 is neither the first (1) nor the last (3) -- it is just where the halving landed. Finding the first requires the lower_bound template — The exact search stops at the first match it happens to hit, which depends entirely on the midpoint arithmetic. No adjustment of the comparisons fixes it -- you need the boundary template, which keeps narrowing after a match instead of returning. That is the whole reason lower_bound and upper_bound exist alongside the exact search.

2. How do you count occurrences of x in a sorted array in O(log n)?

   A Find x, then scan left and right B upper_bound(x) - lower_bound(x) C Two exact searches and subtract the indices D It requires O(n) in the worst case
   pch.quizShowAnswer

   B — upper_bound(x) - lower_bound(x) — Verified: for target 2 in [1,2,2,2,5,8] that is 4 - 1 = 3. Scanning outward from a hit is O(k) in the number of duplicates, so an array of n identical values makes it O(n) -- correct but not logarithmic, and that is exactly the case an interviewer will reach for.

3. Why does the boundary template use `hi = mid` while the exact search uses `hi = mid - 1`?

   A To avoid a negative index B In an exact search you have proved a[mid] != target so mid is discardable; in a boundary search mid is still a candidate for the answer C Because the boundary template starts hi at len(a) D To make the loop run one fewer iteration
   pch.quizShowAnswer

   B — In an exact search you have proved a[mid] != target so mid is discardable; in a boundary search mid is still a candidate for the answer — The two mismatches are the source of nearly every binary-search bug. `while lo < hi` with `hi = mid - 1` discards a candidate it never disproved, so it silently skips the answer. `while lo <= hi` with `hi = mid` never shrinks the window when lo == hi, so it hangs forever. Keep the pairs together.

4. In the lower_bound template, why does `hi` start at `len(a)` rather than `len(a) - 1`?

   A To avoid an off-by-one in mid B So that len(a) is a reachable answer -- a target larger than everything has its insertion point one past the end C Because the loop condition is `lo < hi` D It does not matter
   pch.quizShowAnswer

   B — So that len(a) is a reachable answer -- a target larger than everything has its insertion point one past the end — Verified: target 9 on a 6-element array returns 6, and target 0 returns 0. Both are legal insertion points, and 6 is unreachable if hi starts at 5. This is why lower_bound doubles as "where would x go?" -- which is LC 35 in its entirety -- and why it returns a position rather than -1 for a missing value.

5. Can binary search work on an array that is not sorted?

   A No -- sortedness is the precondition B Yes, when a monotonic predicate exists: peak finding works on arbitrary input because "the surviving range contains a peak" is preserved every step C Only if the array is rotated-sorted D Only for arrays of distinct values
   pch.quizShowAnswer

   B — Yes, when a monotonic predicate exists: peak finding works on arbitrary input because "the surviving range contains a peak" is preserved every step — The requirement is the ability to discard half *with certainty*. Sortedness is one way to earn that, not the definition. Peak finding (LC 162) is the cleanest counterexample -- nothing about the input is ordered, yet each comparison of a[mid] against a[mid+1] rules out one side for good.

6. `(lo + hi) // 2` is often written `lo + (hi - lo) // 2`. Does it matter in Python?

   A Yes -- Python ints overflow at 2^63 B No -- Python integers are arbitrary precision. The idiom exists for C++/Java, where lo + hi can overflow a 32-bit int C Yes -- the two expressions give different midpoints D Only for arrays longer than 2^31
   pch.quizShowAnswer

   B — No -- Python integers are arbitrary precision. The idiom exists for C++/Java, where lo + hi can overflow a 32-bit int — The two expressions are mathematically identical and Python cannot overflow, so either is fine here. Being able to say *why* the defensive form exists -- rather than copying it as a ritual -- is what the question is testing, and it matters the moment the interviewer's language is not Python.

7. Roughly how many iterations does a binary search take on n = 10^9?

   A About 1,000 B About 30, since 2^30 is roughly 10^9 C About 10 D About 10^4.5
   pch.quizShowAnswer

   B — About 30, since 2^30 is roughly 10^9 — log2(10^9) is just under 30. This is the arithmetic that makes "binary search on the answer" viable over enormous value ranges -- a range of 10^18 is only about 60 probes. Being able to produce that number quickly is what lets you argue an approach fits inside the time limit.

Recall card

• Two templates, never mixed: exact value -> lo <= hi, hi = mid - 1, return inside the loop. Boundary -> lo < hi, hi = mid, return lo after.
• hi = mid because mid may be the answer. lo < hi with hi = mid - 1 skips it; lo <= hi with hi = mid hangs.
• Exact search returns an index, not the first. On [1,2,2,2,5,8] target 2 gives index 2 — neither end.
• lower_bound = bisect_left, upper_bound = bisect_right. Verified identical. Count of x is upper - lower (3 for three 2s).
• In the bound templates hi starts at len(a), so a too-large target returns len(a) — a legal insertion point. That makes lower_bound the answer to LC 35.
• A missing value still returns its insertion position, not -1.
• The precondition is a monotonic predicate, not sortedness. Peak finding needs no order at all.
• Termination: under lo < hi and floor division, mid < hi, so hi = mid always shrinks.
• lo + (hi - lo) // 2 matters in C++/Java, never in Python.
• ~30 iterations at $n = 10^9$, ~60 at $10^{18}$ — the arithmetic behind binary search on the answer.

Recap

• One template, two flavors: lo <= hi with inclusive bounds for exact matches; lo < hi with an exclusive hi for boundary-finding (lower_bound/upper_bound).
• mid = lo + (hi - lo) // 2 is an overflow-free habit worth keeping even in Python, where integers never actually overflow.
• bisect.bisect_left / bisect.bisect_right are lower_bound / upper_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 hi 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.