TL;DR: You can whiteboard binary search perfectly. You can explain the invariant, walk through the halving logic, nail the termination condition — and then open a contest problem, stare at it for eight minutes, and submit a solution with mid + 1 where it should be mid.

📖 Reading time: ~44 min

What's in this article

Why Binary Search Trips You Up Even After You 'Get It'
The Mental Model That Actually Sticks: Invariants, Not Midpoints
Python's bisect Module: What It Does and Where It Breaks
The Four Templates You Need to Internalize
Binary Search on the Answer: The Pattern That Unlocks Hard Problems
Off-By-One Errors: The Exact Lines That Cause Them
Codeforces-Specific Patterns That Show Up Constantly
Rotated Arrays and 2D Matrices: Where Binary Search Gets Weird

Why Binary Search Trips You Up Even After You 'Get It'

You can whiteboard binary search perfectly. You can explain the invariant, walk through the halving logic, nail the termination condition — and then open a contest problem, stare at it for eight minutes, and submit a solution with mid + 1 where it should be mid. Wrong answer. You tweak it. Wrong answer again. Time's up. I've done this more times than I want to admit, and the brutal truth is that understanding the algorithm and reliably implementing it under pressure are two completely different skills.

The specific failure mode looks like this: you can explain binary search to a junior dev at a whiteboard without hesitation, but on a medium-difficulty LeetCode problem — say, "Find First and Last Position of Element in Sorted Array" — you start second-guessing whether your loop should be while lo < hi or while lo <= hi, whether to return lo or lo - 1, and whether mid = (lo + hi) // 2 or mid = (lo + hi + 1) // 2. Every variation feels like it might be right. None of them feel certain. That uncertainty is the enemy, and it compounds hard when you're 20 minutes into a 35-minute round.

The root cause isn't that you don't understand binary search. The root cause is that you've never committed to a single, rigid template and practiced it until it's automatic. Most developers learn binary search from three different sources — a textbook, a YouTube video, a blog post — each using slightly different conventions. So your mental model is a Frankenstein's monster of half-remembered variations, and your brain has to negotiate between them mid-contest. That negotiation is where the off-by-one errors live.

Here's what this guide actually covers, in concrete terms:

One canonical template per search type — lower bound, upper bound, and arbitrary predicate searches — written in Python, with the exact reasoning for every boundary decision baked in
Python's bisect module — when to trust it, when it'll mislead you because your problem isn't quite a standard lookup, and the one-liner patterns that show up constantly on LeetCode
The predicate reframe — the mental model shift that makes "search on the answer" problems (Codeforces loves these) click immediately instead of feeling like a different algorithm entirely
Contest-specific patterns — the exact problem shapes that binary search solves on Codeforces Div. 2 C/D problems and LeetCode mediums, so you recognize them fast under time pressure

One thing that genuinely accelerated my practice: using AI tools to stress-test my implementations. I'd write a binary search solution, then prompt an AI to generate brute-force versions and edge case inputs to compare outputs against. It's not about having the AI write your code — it's about getting instant feedback loops during practice without having to handcraft test cases. For that kind of workflow, check out the Best AI Coding Tools in 2026 (thorough Guide) — some of the options there are specifically strong at code analysis and generating adversarial test inputs.

The thing that caught me off guard when I finally fixed my binary search reliability wasn't a new insight into the algorithm — it was realizing I needed to stop thinking and start pattern-matching. Expert competitive programmers don't reason through their binary search template from first principles mid-contest. They have one template burned into muscle memory, and they apply it. The goal of this guide is to give you that template, explain exactly why it's structured the way it is so you trust it completely, and then show you how to map contest problems onto it fast.

The Mental Model That Actually Sticks: Invariants, Not Midpoints

Most binary search bugs aren't logic bugs — they're model bugs. The developer is thinking "where is the midpoint?" when they should be thinking "what is always true about lo and hi?" I spent an embarrassing amount of time writing mid = (lo + hi) // 2 and then immediately getting confused about whether the answer was lo, hi, or mid at termination. The moment I switched to thinking in invariants instead, the off-by-one errors stopped. Not reduced — stopped.

Here's the contract that actually works. Pick one of two stances and commit to it for the entire function:

Stance A: lo is always a valid candidate answer. hi is always out of bounds — it has been ruled out. The answer lives in [lo, hi).
Stance B: lo is always below the answer. hi is always a valid candidate or the answer itself. The answer lives in (lo, hi].

Both are correct. Mixing them mid-function is how you get lo + 1 off-by-ones at 2 AM during a contest. I personally use Stance A for everything — it maps directly to Python's bisect_left semantics and the invariant is easy to state out loud: "hi has been eliminated, lo has not." Every time you shrink the window, you have to preserve that contract. That's it. That's the whole model.

To make this concrete, here's leftmost insertion point — the bisect_left behavior — written explicitly so you can see the invariant doing the work:

def leftmost_insertion(nums: list[int], target: int) -> int:
    # Invariant: answer lives in [lo, hi)
    # lo is always a valid candidate, hi is always eliminated
    lo, hi = 0, len(nums)  # hi = len(nums) means "past the end" — already out of bounds

    while lo < hi:
        mid = lo + (hi - lo) // 2  # avoids overflow; same as (lo+hi)//2 in Python but good habit

        if nums[mid] < target:
            lo = mid + 1  # mid is too small, so mid is eliminated; lo moves up
        else:
            hi = mid      # mid could be the answer, but everything above it is eliminated

    return lo  # lo == hi; the only remaining candidate

Notice why this kills off-by-one errors before they happen. You never ask "should I return lo or hi?" Because at termination lo == hi, and your invariant told you from line one that lo is the answer. There's no decision to make. The thing that caught me off guard when I first learned this framing: you almost never touch hi in the return statement when using Stance A. If you find yourself returning hi - 1 or doing post-loop adjustments, that's a smell that the invariant drifted somewhere in the loop body.

One specific gotcha: initializing hi = len(nums) - 1 instead of hi = len(nums) is the single most common mistake and it breaks the invariant immediately. If the target belongs at the very end of the list, len(nums) - 1 has already eliminated the correct answer before the loop even runs. Set hi = len(nums), accept that hi starts out of bounds, and trust the contract. The loop will never dereference nums[hi] because mid always lands strictly between lo and hi when the window has size ≥ 2.

Python's bisect Module: What It Does and Where It Breaks

The thing that trips people up most with bisect isn't the API — it's the silent failure mode. Pass it a descending list, get back a garbage index, submit your solution, get Wrong Answer, spend 45 minutes debugging logic that's actually fine. I've been there. The module does zero validation on your input. If your list isn't sorted ascending, it will return a position with complete confidence and zero correctness. That's the gotcha nobody puts in the tutorial.

Once you've internalized that, the actual API is clean. Import it like this:

from bisect import bisect_left, bisect_right, insort

The difference between bisect_left and bisect_right is exactly one edge case: duplicate values. bisect_left([1,2,2,3], 2) returns 1 — the leftmost position where 2 could go without disturbing the sort. bisect_right([1,2,2,3], 2) returns 3 — just past the last 2. When there are no duplicates, they're identical. When there are, pick wrong and your count-of-elements logic breaks in ways that look like off-by-one errors.

When bisect is enough — and when it isn't

bisect covers a solid chunk of competitive programming binary search problems: finding insertion points, counting elements less than X, checking if a value exists, lower/upper bound queries on a static sorted structure. insort handles insertion while maintaining order, though O(n) shifting means it's only practical on small lists — don't use it inside a tight loop on 105 elements. Where bisect falls short is when your search space isn't a concrete list at all. Problems like "find the minimum speed such that all packages arrive on time" require you to binary search over an implicit answer space. There's no list to pass in — you write the loop yourself, define a custom feasibility check, and run the search manually. That pattern is actually more common in harder problems than direct array lookup.

The Python 3.10 key parameter — verify your judge version first

Python 3.10 added a key parameter to bisect_left and bisect_right, which lets you search on a changed value without pre-sorting a secondary structure. Before 3.10, if you needed to binary search on, say, the second element of tuples, you either maintained a parallel sorted list or wrote your own loop. Most competitive programming judges lag behind — Codeforces runs Python 3.8 and PyPy 3.9 as of my last check, which means no key parameter. If you write code locally on 3.10+ using key= and submit, it will explode with a TypeError. Always check the judge's language version in the submission dropdown before you rely on newer stdlib features.

My actual workflow: I use bisect_left and bisect_right as fast utilities for the simple cases and reach for a manual lo, hi, mid loop the moment the problem adds any custom condition — monotonic function over an answer range, floating point bounds, circular arrays, anything non-trivial. The module shines brightest when the boilerplate would slow you down in a timed contest. It's fast to type, fast to read back, and battle-tested. But treating it as a general binary search solution rather than a sorted-array utility is how you accumulate confusing WAs.

The Four Templates You Need to Internalize

Template 1: Classic Find-Exact-Value

Most people learn binary search like this, and honestly, it's fine for warm-up problems. The idea is simple: you have a sorted array, you want to know if a value exists, and you return its index or -1. Here's the version I actually use:

def binary_search(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # avoids overflow, habit from C++ days
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

The lo + (hi - lo) // 2 trick is worth internalizing even in Python, because Python handles arbitrary integers natively. The habit carries over when you're writing in C++ under contest pressure and you forget that int overflows at ~2.1 billion.

Template 2: Find Leftmost Position Where Condition Turns True

This is the template I wish someone had beaten into my head earlier. Half the binary search problems in competitive programming aren't asking "does this value exist?" They're asking "what's the first position where X becomes true?" — find the first index where the value is ≥ target, find the first bad version in a CI pipeline, find the minimum speed that lets a worker finish in time. The shape is always the same:

def find_left(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr)  # note: hi = len(arr), not len(arr) - 1
    while lo < hi:         # note: strict less-than, not <=
        mid = lo + (hi - lo) // 2
        if condition(mid):  # replace with your actual predicate
            hi = mid        # don't do mid - 1 here
        else:
            lo = mid + 1
    return lo  # lo == hi, this is your answer

The gotcha that catches everyone at least once: hi starts at len(arr), not len(arr) - 1. That's because the answer might be "no valid position exists" — in which case you want lo to land at len(arr) as a sentinel. If you set hi = len(arr) - 1, you'll silently return a wrong answer on edge cases and spend 40 minutes wondering why your solution fails on the last test case.

Template 3: Find Rightmost Position Where Condition Is Still True

This is Template 2's mirror. You want the last index where something holds — the latest deadline you can still meet, the maximum mid-point where you can achieve a goal. One clean way to implement it is to just flip the predicate and use Template 2, then subtract 1. But if you prefer a direct version:

def find_right(arr: list[int], target: int) -> int:
    lo, hi = -1, len(arr) - 1  # lo = -1 as sentinel for "nothing found"
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # ceiling division — critical here
        if condition(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

That (hi - lo + 1) // 2 is the part people get wrong most often. Without the +1, when hi - lo == 1, mid always equals lo, your condition passes, you set lo = mid... and you've got an infinite loop. I've shipped that bug into a contest twice. The ceiling division breaks the symmetry and keeps the loop terminating.

Template 4: Binary Search on the Answer

This is where competitive programming binary search gets actually interesting. The array isn't given to you — you're searching over a range of possible answers and checking feasibility at each midpoint. Classic examples: "what's the minimum number of days to ship all packages?", "what's the smallest maximum sum when splitting an array into K subarrays?", "what's the largest minimum distance between placed elements?" The structure is always: pick a candidate answer, write a greedy feasibility check, binary search over the candidates.

def solve():
    # Example: minimum max-sum to split array into k subarrays
    def feasible(max_sum: int) -> bool:
        chunks, current = 1, 0
        for num in nums:
            if current + num > max_sum:
                chunks += 1
                current = 0
            current += num
        return chunks <= k

    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

The real skill here isn't the binary search itself — it's writing the feasible() function correctly and figuring out the right search boundaries. A wrong upper bound is a silent bug. For most "minimum maximum" problems, lo = max(arr) and hi = sum(arr) is the right instinct. For "maximum minimum" problems, flip it.

Why You Only Need to Commit One Template to Muscle Memory

Here's my honest take: Template 2 (leftmost true) is the one worth owning completely. Template 1 is just Template 2 with an equality check bolted on — once you have a candidate position from Template 2, you verify arr[lo] == target and return lo or -1. Template 3 is Template 2 with a negated predicate plus a -1 offset. Template 4 uses Template 2's exact loop structure, just with a synthetic search space instead of a real array. Under contest pressure, you don't want four half-remembered templates fighting each other in your head. You want one clean mental model with known mutation rules. The mutation is: if you need the rightmost, flip the predicate and adjust by one. Everything else is the same loop.

Binary Search on the Answer: The Pattern That Unlocks Hard Problems

The Core Idea: You're Not Searching a List

Most people hit a wall with binary search problems because they keep thinking about it as "find X in a sorted array." Binary search on the answer flips this completely. Instead of searching through data, you're searching through the space of possible answers. You pick a candidate answer, ask "is this feasible?", and use that yes/no signal to cut your search space in half. That's it. Once this clicked for me, a whole class of problems that felt like DP or greedy suddenly became obvious.

Take Koko Eating Bananas (LeetCode 875). Koko can eat k bananas per hour. Given piles and a time limit h, find the minimum k that lets her finish. The naive approach is trying every possible speed. But notice: if speed k works, then speed k+1 also works. If speed k doesn't work, then k-1 won't either. That monotonic relationship — feasible above some threshold, infeasible below it — is the entire unlock. You binary search over speeds from 1 to max(piles), and for each candidate speed you just simulate whether she finishes in time.

The Two-Question Checklist Before You Write a Single Line

Before coding, I force myself to answer both of these:

Is the answer space monotonic? Can you say "if X works, then X+1 also works" (or the reverse)? If you can't say this confidently, binary search on the answer is the wrong tool.
Can you write a feasibility check in reasonable time? If your feasibility check itself is O(n²), you haven't saved much. The power of this pattern is O(log(range)) × O(check_cost). Check cost should be O(n) or O(n log n).

If you answer yes to both, write the feasibility function first and ignore the binary search scaffold entirely for a few minutes. This is the habit that separates people who consistently solve hard problems from people who panic. The feasibility function is the problem. The binary search is just bookkeeping around it.

Full Walkthrough: Minimum Number of Days to Make M Bouquets

LeetCode 1482: Given a bloom day array, you need m bouquets each requiring k adjacent flowers. Find the minimum number of days to wait. The answer space is days — from 1 to max(bloomDay). Waiting more days is always at least as good (more flowers bloom), so it's monotonic. Feasibility check: given day, count how many bouquets you can make by only counting consecutive runs of bloomed flowers.

from math import ceil
from typing import List

def minDays(bloomDay: List[int], m: int, k: int) -> int:
    # Early exit: impossible regardless of days
    # n flowers, need m*k total — if we don't have enough, return -1 immediately
    n = len(bloomDay)
    if m * k > n:
        return -1

    def can_make(day: int) -> bool:
        """
        Returns True if, by waiting `day` days,
        we can make at least m bouquets of k adjacent bloomed flowers.
        """
        bouquets = 0
        consecutive = 0  # current streak of bloomed flowers
        for bloom in bloomDay:
            if bloom <= day:
                consecutive += 1
                # Complete a bouquet when we hit k consecutive flowers
                if consecutive == k:
                    bouquets += 1
                    consecutive = 0  # reset — can't reuse flowers
            else:
                consecutive = 0  # broken streak
        return bouquets >= m

    # lo: smallest possible answer (at least one flower must bloom)
    # hi: latest we'd ever need to wait (last flower blooms)
    lo, hi = min(bloomDay), max(bloomDay)

    # Standard binary search — we want the leftmost True
    while lo < hi:
        mid = (lo + hi) // 2
        if can_make(mid):
            hi = mid   # mid works, try to go lower
        else:
            lo = mid + 1  # mid doesn't work, need more days

    return lo

A few things to notice. The consecutive = 0 reset inside the bouquet completion is the subtle part — flowers used for one bouquet can't be reused. I've seen people miss this and pass easy test cases but fail on inputs where adjacent groups chain together in unexpected ways. Also, lo = min(bloomDay) not 1. If your lower bound is 1 and the minimum bloom day is 100,000, you're doing extra iterations for no reason. It doesn't change correctness but it's sloppy and in a contest, clear thinking matters.

The Bounds Bug That Will Eat Your Contest Time

The single most common mistake I see — and made myself for embarrassingly long — is setting lo and hi wrong at the boundaries. Two failure modes:

Off-by-one at hi: Setting hi = max(bloomDay) - 1 because "surely we don't need the last day." You do. When only one flower exists and it blooms on the last day, your search never considers the correct answer.
Using 0 as lo when 0 is invalid: If 0 days means nothing bloomed and that's guaranteed infeasible, your feasibility check handles it fine — but it's cleaner and safer to start lo at a value you know is at least plausible. It forces you to think about the domain instead of lazily defaulting to 0 and infinity.

The way I debug bounds bugs fast: before running, manually check can_make(lo) and can_make(hi). At lo, the function should return False (or at least, you understand why it might). At hi, it should return True — if your upper bound doesn't guarantee feasibility, your binary search will return a wrong answer silently. No exception, no obvious error. That silence is what makes bounds bugs so expensive.

Off-By-One Errors: The Exact Lines That Cause Them

The line that's bitten me more than any other in competitive programming: while lo <= hi when I should have written while lo < hi. These two conditions aren't interchangeable style choices — they imply entirely different invariants, and mixing them up produces infinite loops or skipped answers that are absolutely brutal to debug under contest pressure.

Here's the mental model I use. while lo < hi is a half-open interval approach — your search space is [lo, hi) and the loop exits when lo == hi, meaning you've converged to a single candidate. You never evaluate the midpoint directly as your answer inside the loop; the answer lives at lo after the loop ends. while lo <= hi is a closed interval approach — the search space is [lo, hi] and you're checking mid directly on each iteration. If arr[mid] == target, you return immediately. The loop exits when lo > hi, meaning the target genuinely isn't there. Use lo <= hi when you're doing exact-match search with an early return. Use lo < hi when you're finding a boundary — leftmost insertion point, first element satisfying a predicate, that kind of thing.

# Exact match — closed interval, early return
def binary_search_exact(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# Left boundary — half-open interval, answer at lo after loop
def binary_search_left(arr, target):
    lo, hi = 0, len(arr)  # note: hi = len(arr), not len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

About mid = lo + (hi - lo) // 2 — yes, Python integers don't overflow. You could write (lo + hi) // 2 and it would work fine. I still write it the long way, and I'd tell any junior to do the same. The habit matters because the moment you port your logic to C++, Java, or Go in an interview or a polyglot contest, (lo + hi) / 2 will silently overflow on large inputs and hand you a wrong answer with no error message. Burning the safe form into muscle memory costs you nothing in Python and saves you real pain everywhere else.

Now the update rules, because this is where the pairing matters. With while lo < hi, you must use hi = mid (not mid - 1) when the right side shrinks. If you write hi = mid - 1, you can skip the actual answer. But with while lo <= hi, you must use hi = mid - 1 — writing hi = mid when lo == hi == mid creates an infinite loop because nothing moves. The pairs are: (lo < hi) goes with (hi = mid), and (lo <= hi) goes with (hi = mid - 1). Treat them as locked sets. Never mix and match.

while lo < hi + hi = mid + lo = mid + 1 — correct, terminates
while lo <= hi + hi = mid - 1 + lo = mid + 1 — correct, terminates
while lo < hi + hi = mid - 1 — danger: can skip the answer on size-2 arrays
while lo <= hi + hi = mid — infinite loop when lo == hi

The debugging trick I now do before every submission: test with an array of length 1 and an array of length 2, targeting both elements that exist and one that doesn't. These tiny cases stress every edge of your loop condition and update rules. A length-1 array catches cases where your loop never runs or runs once but computes the wrong mid. A length-2 array is where hi = mid vs hi = mid - 1 diverges — the midpoint rounds down, so mid == lo, and if your update doesn't move hi strictly below mid, you're stuck. Takes 90 seconds to run these checks mentally or throw them into a scratch cell. It's caught wrong submissions for me more times than I'd like to admit.

Codeforces-Specific Patterns That Show Up Constantly

The pattern that unlocked binary search for me wasn't the classic "find element in sorted array" — it was recognizing the phrase "minimize the maximum" or "maximize the minimum" in a problem statement. Once you see that framing, your brain should immediately fire: binary search on the answer. Problems like "split an array into K groups to minimize the maximum sum" or "place M facilities to maximize the minimum distance between them" all share the same structure. You're not searching a data structure — you're searching the answer space itself. The answer is monotonic: if a certain value is achievable, anything worse is also achievable. That monotonicity is all you need to binary search.

Parametric Search: The Mental Model

Here's how I frame it every time. Ask: "Can I achieve answer X?" If yes for X, is it also yes for X-1 (in a minimization problem)? If that's true, you have a boolean function over a sorted domain. Binary search finds the boundary. The hard part is never the binary search skeleton — it's writing the feasibility check. For "split array into at most K subarrays where max subarray sum ≤ mid", the check is a greedy scan: accumulate elements until adding the next would exceed mid, then start a new group. Count groups. If count ≤ K, it's feasible.

def can_split(nums, k, max_sum):
groups = 1
current = 0
for n in nums:
if n > max_sum:
return False
if current + n > max_sum:
groups += 1
current = 0
current += n
return groups <= k

lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo + hi) // 2
if can_split(nums, k, mid):
hi = mid
else:
lo = mid + 1

print(lo)

The feasibility function here is O(n). You call it O(log(sum - max)) times. That's your O(n log n) — or more precisely O(n log S) where S is the answer range. This pattern covers probably 60% of the Div. 2 C and D problems tagged "binary search" on Codeforces. The greedy inside the feasibility check is almost always a left-to-right scan, a sort-then-greedy, or a BFS/DFS over a graph. If the check requires anything heavier than O(n log n), you're probably solving the wrong subproblem.

Segment Boundaries and Coordinate Compression

Binary search also shows up when you need to work with large coordinate spaces but only care about a subset of "interesting" values. The classic setup: you have N events on a number line that goes up to 109, but only N distinct x-values matter. Compress them to [0, N-1], then binary search within that compressed space. Python's bisect module handles this directly:

import bisect

coords = sorted(set(all_x_values))

def compress(x):
return bisect.bisect_left(coords, x)

To find the first coordinate >= query:

idx = bisect.bisect_left(coords, query)

The gotcha that burned me once: bisect_left vs bisect_right matters when you have duplicates or when you're looking for "strictly greater than" vs "greater than or equal to." bisect_left gives you the insertion point before any existing entry, bisect_right after. For segment problems where you're finding which interval a query point falls into, getting this wrong shifts your answer by one index and produces wrong answers that look almost right — the worst kind of bug in a contest.

Real Problem Walkthrough: Codeforces 1030C

Let's do a live example. CF 1030C — "Vasya and Golden Ticket" style problems aside, let me walk through a problem structure I hit often: you have an array and need to find the minimum number of operations to make all elements ≤ some threshold, where each operation affects a contiguous subarray. Binary search on the number of operations. Feasibility check: greedy left to right, apply an operation wherever needed, count. If count ≤ mid, feasible.

My actual 10-minute process on Codeforces: read the problem, circle the output (single number, usually), ask "is this answer monotone?" If yes, set lo and hi to the tightest bounds I can prove (never 0 to 1018 unless you have to — tight bounds speed things up and reduce off-by-one risk), write the feasibility function, plug into the template below, test on the examples, submit.

import sys
input = sys.stdin.readline

def feasible(mid):
# problem-specific greedy check
pass

def solve():
# read input
lo, hi = 0, 10**9 # tighten these to the actual answer range
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
print(lo)

solve()

One thing that tripped me up early: the direction of the binary search. For "minimize X", you want the smallest mid where feasible(mid) is True — so when it's feasible, you go left (hi = mid). For "maximize X", you want the largest mid where feasible, so when it's feasible you go right (lo = mid) and use mid = (lo + hi + 1) // 2 to avoid infinite loops. Getting the ceiling vs floor wrong causes an infinite loop at the boundary — I've wasted 20 minutes on this. The fix is mechanical: if you write lo = mid, always write mid = (lo + hi + 1) // 2. No exceptions.

Rotated Arrays and 2D Matrices: Where Binary Search Gets Weird

The Rotated Array Problem Will Catch You Off Guard

The first time I hit a rotated sorted array problem in a contest, I spent 20 minutes debugging what looked like a perfectly correct binary search. The array [4, 5, 6, 7, 0, 1, 2] is sorted — just with a pivot in the middle — and your standard lo, hi, mid template has no idea how to handle it. The standard template assumes arr[lo] <= arr[mid] <= arr[hi]. Rotation destroys that guarantee, so you get wrong comparisons and silently incorrect answers. No crash, no obvious bug. Just wrong output.

The fix relies on one insight that took me a while to internalize: when you split a rotated sorted array at any midpoint, at least one of the two halves is always cleanly sorted. Always. No exceptions. This is the key that unlocks the whole problem. Once you know which half is properly sorted, you can check if your target falls within that range using a simple bounds check, and if it does, you binary search there. If not, you recurse into the messy half. Here's the implementation I use:

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        # Left half is sorted
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

The gotcha I see juniors hit repeatedly: the condition is nums[lo] <= nums[mid], not <. You need the equals sign to handle duplicate-adjacent cases and two-element arrays correctly. If you swap it for a strict less-than, you'll get wrong answers on inputs like [3, 1]. LeetCode 33 is the canonical version of this problem — run your solution against it with [3,1] and [1] before you trust it.

Row-Wise Sorted Matrix: Just Flatten It With Math

For a matrix where each row is sorted and the last element of each row is smaller than the first element of the next row (LeetCode 74), binary search is almost embarrassingly straightforward once you see it. The matrix is a sorted array — it's just stored in 2D. You run a standard binary search over the virtual index range [0, m*n - 1], and convert back to 2D coordinates on every midpoint check with row = mid // n and col = mid % n. That's the whole trick.

def search_matrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = matrix[mid // n][mid % n]
        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

O(log(m*n)) time, zero extra space, clean loop. If you're reaching for nested binary search — outer search for the row, inner search within the row — that's also O(log m + log n) which equals O(log(m*n)), so it's the same complexity. I prefer the flattened version because it's one loop, fewer variables, and harder to accidentally off-by-one on the row boundary.

The Fully Sorted-Row-And-Column Matrix Is a Different Animal

Now here's where people get burned: LeetCode 240, where each row is sorted left-to-right and each column is sorted top-to-bottom, but the rows are not ordered relative to each other. Binary search alone cannot solve this efficiently. The reason is that when you pick a midpoint, you have no clean way to eliminate a full half of the search space because the target could live in multiple quadrants simultaneously. I've watched people waste 45 minutes in a contest trying to make binary search work here. Don't be that person.

The correct algorithm is the staircase search: start at the top-right corner (or bottom-left — pick one and commit). If the current value equals the target, you're done. If it's greater than the target, move left — you've eliminated the entire current column below you. If it's less than the target, move down — you've eliminated the entire current row to the left. Each step eliminates one row or one column, so you do at most m + n steps. That's O(m + n) time. Binary search gives you O(n log m) if you binary search every row, which is actually worse when the matrix is square.

def search_matrix_ii(matrix, target):
    if not matrix:
        return False
    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1
        else:
            row += 1
    return False

The conceptual leap here matters: binary search is optimal when you can cleanly bisect a totally ordered sequence. The moment you're dealing with a partial order — where things are sorted along two axes independently — you need an algorithm designed for that structure. Reaching for binary search by default is the wrong instinct. Recognizing the problem shape and matching it to the right traversal strategy is the actual skill competitive programming builds.

Practice Problems Ordered by Pattern (Not Just Difficulty)

Most people grind binary search problems in order of difficulty and then wonder why they keep freezing on medium-hards. The difficulty rating is nearly useless for building intuition. What actually works is grinding by pattern — because binary search has about four distinct mental models, and conflating them is exactly what causes bugs at 2am during a contest.

Starter Problems: Get the Loop Right First

Before anything else, burn these three into muscle memory:

LeetCode 704 – Binary Search: Pure template. Your only job here is to decide whether you use while lo <= hi or while lo < hi and then be consistent. I use lo <= hi with mid = lo + (hi - lo) // 2 and explicitly return -1 at the end. Avoid mid = (lo + hi) // 2 — Python handles big integers natively so it won't overflow like in C++, but building the safe habit now pays off when you port logic.
LeetCode 35 – Search Insert Position: Forces you to think about what the loop returns when the target doesn't exist. This is where most people realize they don't actually understand their own template.
LeetCode 374 – Guess Number Higher or Lower: Wraps the same logic in an API call. Good for practicing the mental separation between "binary search skeleton" and "the condition I'm evaluating."

# Template I actually use — commit to it and stop reinventing
def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Invariant Practice: When the Answer Isn't a Direct Lookup

This is the category that separates people who "know binary search" from people who can actually use it. LeetCode 34 (Find First and Last Position) is the canonical invariant problem — you need to find the leftmost and rightmost occurrence separately, which means writing two slightly different binary searches. The thing that caught me off guard the first time was that both searches look almost identical but differ in one comparison operator. One uses <, the other uses <=. Get that wrong and you're off by one in a way that's genuinely hard to debug under pressure.

LeetCode 153 (Find Minimum in Rotated Sorted Array) is harder because there's no target — you're searching for a property, not a value. The invariant you maintain is: "the answer is always within [lo, hi]." You shrink the window by comparing nums[mid] to nums[hi] to decide which half is sorted. If you find yourself confused about whether to move lo or hi, write out a concrete 5-element rotated array and trace through it by hand. Do this every time until it feels automatic, not just once.

Binary Search on the Answer: The Technique That Unlocks Hard Problems

This pattern has a completely different setup. You're not searching an array — you're searching a range of possible answers and asking a yes/no feasibility question at each midpoint. Once you see it, you'll spot it everywhere.

LeetCode 875 – Koko Eating Bananas: Binary search over eating speed k. The feasibility function checks if Koko can finish all piles in h hours at speed k. Start here — the feasibility check is a clean one-liner.
LeetCode 1011 – Capacity To Ship Packages: Same skeleton, slightly messier feasibility check. The bounds are lo = max(weights) (minimum possible capacity) and hi = sum(weights) (ship everything in one trip). Getting the bounds right is half the problem.
LeetCode 410 – Split Array Largest Sum: This one bites people because it's rated Hard and the feasibility function requires careful greedy logic inside it. But the binary search shell is identical to 875 and 1011. Solve 875 and 1011 first, then this one becomes "hard greedy inside easy binary search."

# Generic "binary search on answer" shell
def solve(data, limit):
    def feasible(mid):
        # return True if mid satisfies the constraint
        pass

    lo, hi = lower_bound(data), upper_bound(data)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid          # mid might be the answer, don't exclude it
        else:
            lo = mid + 1
    return lo

Codeforces Problems Worth Grinding

LeetCode problems are clean and well-defined. Codeforces problems will make you uncomfortable in the right ways — messier problem statements, tighter time limits, edge cases you wouldn't expect. These three are worth the time:

CF 460C – Present: Binary search on the answer with a bitwise XOR twist in the feasibility check. Tests whether you can binary search when the feasibility function itself isn't trivial.
CF 812C – Sagheer and Nubian Market: Binary search on the number of items you buy. The interaction between the binary search variable and the cost function is non-obvious. Spend time understanding why you're binary searching over what you're binary searching over.
CF 1598D – Painting the Array II: Harder. Requires combining binary search with greedy. Do this in week two, not week one.

The 2-Week Structured Block

Don't treat this as a casual problem-per-day list. Run it like this:

Days 1–2: 704, 35, 374. Write the same template three times from scratch. No copy-paste.
Days 3–5: 34 and 153. After solving, write down in plain English what invariant you maintained. If you can't articulate it, re-solve it.
Days 6–9: 875, 1011, 410, in that order. For each, write the feasibility function first, then wrap it in the binary search shell. The separation matters — it keeps the code readable and the logic debuggable.
Days 10–14: CF 460C, CF 812C, then CF 1598D. Give yourself at least 45 minutes of genuine struggle before looking at editorial hints. The struggle is the point.

After this block, when you see a new problem, you should be asking "which of these four patterns is this?" within the first two minutes of reading. If you're still asking "is binary search even applicable here?" you need another pass through the invariant and answer-search categories — those two are where the real recognition skill lives.

When Binary Search Is the Wrong Tool

Unsorted Input Where Sorting Destroys the Answer

The most common mistake I see in competitive programming is reaching for binary search the moment someone says "find X in a collection." Binary search on an unsorted array gives you garbage — that's obvious. The subtle trap is sorting first and then binary searching, when the position of elements is load-bearing information. Classic example: you're given an array of stock prices indexed by day, and you need to find the first day price exceeds some threshold. If you sort first, you've destroyed the temporal ordering and the problem is now unsolvable. The answer isn't a value — it's an index in the original sequence.

# WRONG approach — sorting destroys the "first occurrence in time" semantics
prices = [100, 95, 110, 88, 120, 105]
prices.sort()  # Now you can binary search, but you've lost which day is which
idx = bisect.bisect_left(prices, 110)  # Meaningless index

# RIGHT approach — linear scan preserves order semantics
def first_day_above(prices, threshold):
    for i, p in enumerate(prices):
        if p >= threshold:
            return i
    return -1

The sorting question to ask yourself: "Does the index in the original array matter?" If yes, binary search is off the table unless you're doing something like binary searching on the answer (a completely different technique) or keeping a parallel index array.

Graph and Tree Problems — BFS/DFS Will Eat Binary Search for Breakfast

I once spent 40 minutes trying to binary search on depth in a tree problem before I slapped myself and wrote a 6-line BFS. The search space in a graph isn't a clean 1D number line. You can't say "go left" or "go right" when you have arbitrary neighbors. If you're trying to find a node, a path, or a reachable state — BFS if shortest path matters, DFS if you need to explore all possibilities. Binary search on a tree makes sense exactly when the tree is a BST and you're exploiting the sorted invariant. Any other tree structure? Forget it.

from collections import deque

def bfs_find(graph, start, target):
    visited = set([start])
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1

Non-Contiguous Search Spaces Break Binary Search on the Answer

Binary search on the answer is one of the most powerful techniques in competitive programming — but it only works when the predicate function is monotone. Meaning: if f(x) is True, then f(x+1) is also True (or False, consistently). The moment your feasibility function has gaps — valid, invalid, valid again — binary search gives you wrong answers silently. This is the sneaky kind of bug because the code structure looks right and it runs without errors.

A concrete situation where this burns you: you're searching for a minimum cost that satisfies some constraint, but the cost function is non-monotone because of weird problem-specific interactions (like a knapsack where adding more capacity sometimes makes things infeasible due to integer constraints). Before committing to binary search on the answer, manually verify the predicate on a few values. If is_feasible(5) is True, is_feasible(6) is False, and is_feasible(7) is True — you need DP or brute force, not binary search.

def is_feasible(mid):
    # Verify this is actually monotone before trusting this binary search
    pass

lo, hi = 0, 10**9
while lo < hi:
    mid = (lo + hi) // 2
    if is_feasible(mid):
        hi = mid
    else:
        lo = mid + 1
# This whole structure silently produces wrong answers on non-monotone predicates

Floating-Point Binary Search: Use Iteration Count, Not Convergence

This one caught me off guard the first time I used floating-point binary search in a geometry problem. The natural instinct is to write while hi - lo > 1e-9 as your convergence condition. Sounds reasonable. In practice, depending on your starting range and the floating-point representation of the values involved, this can loop forever or take an absurd number of iterations due to precision loss around subnormal numbers. The fix is dead simple: use a fixed iteration count. I default to 100 iterations — it gives you roughly 2^-100 relative precision, which is overkill for any judge's floating-point tolerance.

# FRAGILE — can loop forever with bad float values
lo, hi = 0.0, 1e18
while hi - lo > 1e-9:  # Don't do this
    mid = (lo + hi) / 2
    if feasible(mid):
        hi = mid
    else:
        lo = mid

# solid — fixed iteration count
lo, hi = 0.0, 1e18
for _ in range(100):  # 100 iterations gives ~30 decimal digits of precision
    mid = (lo + hi) / 2
    if feasible(mid):
        hi = mid
    else:
        lo = mid
print(hi)  # or (lo + hi) / 2 depending on what you're solving for

The 50-100 iteration range is the community standard for a reason. 50 gives you 2^-50 precision (~15 decimal places), which beats any judge tolerance I've ever seen. 100 is paranoid-safe. The runtime difference between 50 and 100 iterations is negligible unless your feasibility check is genuinely expensive, in which case profile that, not the loop count.

Quick Reference: Python Binary Search Cheat Sheet

Print this out. Tape it to your monitor. I'm serious — the number of times I've fumbled bisect_left vs bisect_right under contest time pressure is embarrassing, and the fix was just having the semantics written down in front of me.

The Two Bisect Calls

import bisect

# bisect_left(a, x) → index i where a[i-1] < x <= a[i]
# Returns the LEFTMOST position where x can be inserted to keep sorted order
# If x exists in a, returns index of the FIRST occurrence
idx = bisect.bisect_left(a, x)   # a[idx] == x (if present)

# bisect_right(a, x) → index i where a[i-1] <= x < a[i]
# Returns the RIGHTMOST position where x can be inserted
# If x exists in a, returns index AFTER the last occurrence
idx = bisect.bisect_right(a, x)  # a[idx-1] == x (if present)

# Practical translation:
# "Does x exist in a?"
found = bisect.bisect_left(a, x) < len(a) and a[bisect.bisect_left(a, x)] == x

# "How many elements equal to x are in a?"
count = bisect.bisect_right(a, x) - bisect.bisect_left(a, x)

# "Largest element <= x"
i = bisect.bisect_right(a, x) - 1   # a[i] if i >= 0

# "Smallest element >= x"
i = bisect.bisect_left(a, x)        # a[i] if i < len(a)

The Four Loop Templates Side by Side

The thing that caught me off guard early on: there's no single "correct" binary search template. Each variant solves a slightly different problem. Mix them up and you get infinite loops or off-by-one bugs. Here they are, pinned:

# Template 1: Find exact target (returns -1 if missing)
lo, hi = 0, len(a) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if a[mid] == target:   result = mid; break
    elif a[mid] < target:  lo = mid + 1
    else:                  hi = mid - 1

# Template 2: Leftmost position satisfying condition (bisect_left equivalent)
# Use when: "find first index where condition is True"
lo, hi = 0, len(a)          # hi = len(a), NOT len(a)-1
while lo < hi:              # strict less-than
    mid = (lo + hi) // 2
    if condition(mid):      hi = mid      # NOT mid-1
    else:                   lo = mid + 1
# Answer is lo (or hi, they're equal)

# Template 3: Rightmost position satisfying condition (bisect_right adjacent)
# Use when: "find last index where condition is True"
lo, hi = 0, len(a)
while lo < hi:
    mid = (lo + hi + 1) // 2   # +1 here prevents infinite loop when lo=hi-1
    if condition(mid):          lo = mid      # NOT mid+1
    else:                       hi = mid - 1
# Answer is lo

# Template 4: Binary search on a real-valued range (no integer mid issues)
lo, hi = 0.0, 1e18
for _ in range(100):            # fixed iterations instead of while; cleaner
    mid = (lo + hi) / 2
    if feasible(mid):   hi = mid
    else:               lo = mid
# Answer is lo (or hi)

The +1 in Template 3's mid = (lo + hi + 1) // 2 trips up almost everyone the first time. Without it, when lo = 4 and hi = 5, mid rounds down to 4, condition is True, so lo = mid = 4... forever. The +1 forces the midpoint to round up when the window is two elements wide, so the loop always makes progress.

Feasibility-Function Skeleton for Binary-Search-on-Answer

Half the hard problems in competitive programming reduce to: "binary search on the answer, then check feasibility." The search itself is mechanical once you have the skeleton. I keep this exact structure copy-pasteable:

def feasible(mid, *args):
    """
    Returns True if 'mid' is an achievable/valid answer.

    Design checklist:
    - Is the predicate monotone? (False...False...True...True OR True...True...False...False)
    - Am I searching for the MINIMUM valid value (use Template 2) or MAXIMUM (Template 3)?
    - Does feasible run in O(n) or O(n log n)? Total complexity = O(log(range) * feasible_cost)
    """
    # Replace with your greedy/simulation check
    total = 0
    for item in args[0]:          # usually iterating input
        total += item
        if total > mid:           # greedy split / reset condition
            total = item
            # count += 1 ...
    return True   # or False based on constraint

# Wiring it up:
lo, hi = MINIMUM_POSSIBLE_ANSWER, MAXIMUM_POSSIBLE_ANSWER
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid):   hi = mid     # searching for minimum valid
    else:               lo = mid + 1
print(lo)

Edge Case Checklist Before You Hit Submit

Run through this mentally every single time. Costs thirty seconds. Saves a wrong answer penalty:

Empty array: Does your code handle len(a) == 0? bisect_left([], x) returns 0 safely, but a[0] after that crashes.
All elements the same: Both bisect calls return predictable indices, but Template 2 and 3 can silently converge to wrong boundaries.
Single element: With lo = 0, hi = 0 and while lo < hi, the loop body never executes. Make sure lo is your answer in that degenerate case.
Target smaller than all elements: bisect_left returns 0. Accessing a[i-1] with i=0 blows up. Guard with if i > 0.
Target larger than all elements: bisect_right returns len(a). Accessing a[i] with i == len(a) blows up. Guard with if i < len(a).
Integer overflow in mid: Not a Python problem (arbitrary precision integers), but if you're computing mid * mid inside feasible() for very large ranges, verify your bounds don't produce astronomical intermediate values that slow things down.
Feasibility predicate not monotone: Binary search is undefined behavior on non-monotone predicates. If your check has a valley or plateau in the middle, you need a different approach entirely.
Off-by-one on answer range: Set lo and hi to the tightest valid bounds you can prove. A common bug is setting hi = max(a) when the answer could be sum(a).

Disclaimer: This article is for informational purposes only. The views and opinions expressed are those of the author(s) and do not necessarily reflect the official policy or position of Sonic Rocket or its affiliates. Always consult with a certified professional before making any financial or technical decisions based on this content.

Originally published on techdigestor.com. Follow for more developer-focused tooling reviews and productivity guides.

How to Actually Master Binary Search in Python for Competitive Programming (Without Just Memorizing Templates)