λDSA Learning Hubpart of DSA Atlas

Searching

Intermediate~3h · 8 lessons12 practice problems

Linear scan to binary search and beyond: lower/upper bounds, search-insert position, rotated arrays, and 'binary search on the answer'.

0 of 8 lessons checked off

Introduction

What it is

  • Searching finds a target — or the boundary where a condition flips — inside a collection. Linear search inspects everything; binary search halves a SORTED (or otherwise monotonic) space each probe.
  • The deep version of this topic isn't 'find x in a list': it's recognising monotonicity. Wherever a yes/no test goes false…false…true…true, binary search finds the flip point in O(log n) — even when the 'array' is a range of candidate answers.

Why it matters

  • O(log n) vs O(n) is the difference between 30 probes and a billion for n = 10⁹.
  • Binary search questions are a FAANG staple precisely because off-by-one errors punish sloppy invariants — they test care, not memory.

How it works

  • Keep an invariant, e.g. 'the answer, if present, lies in [lo, hi]'. Probe mid, use the comparison to discard the half that can't contain the answer, repeat until the range is empty or found.
  • For boundaries (first true / last false), keep [lo, hi) half-open and move the side that preserves 'lo is always ≤ answer < hi'.

Where it's used

  • Database B-tree lookups, git bisect (binary search over commits for the bug-introducing one), autocomplete prefix ranges, and rate limiters searching capacity thresholds.

In interviews

  • Classic: search insert position, first/last occurrence, search rotated array, find peak. Advanced: Koko eating bananas, ship packages in D days, split array largest sum — all 'binary search on answer'.
Analogy: Guess-the-number with 'higher/lower' feedback: each guess kills half the possibilities. Binary search on the answer is the same game where the number is 'the minimum speed that still works' and each guess runs a feasibility test.

Interactive diagram

Every probe halves the live range — 10 elements need at most 4 probes.

Set the search range

The array is sorted — that is the precondition that makes halving legal. Search for 23 in indexes 0..9.

target
23

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Linear search

    The unsorted baseline; early exit; when it's genuinely optimal.

    10 min
  2. Binary search on sorted arrays

    The [lo, hi] invariant, mid arithmetic, and termination.

    25 min
  3. Lower bound and upper bound

    First ≥ x and first > x — the two boundary searches everything reduces to.

    25 min
  4. Search insert position

    Lower bound wearing a different problem statement.

    10 min
  5. Search in rotated sorted arrays

    One half is always sorted — decide which, then discard.

    25 min
  6. Search in a 2-D matrix

    Flatten index arithmetic, or staircase search from a corner.

    15 min
  7. Binary search on the answer

    Monotonic feasibility tests over candidate answers — the pattern behind Koko and friends.

    30 min
  8. Ternary and exponential search (overview)

    Unimodal maxima; unbounded ranges.

    10 min

Operations

Classic binary search

Invariant: the target, if present, is inside [lo, hi]. Compare at mid, discard the impossible half.

Set the search range

The array is sorted — that is the precondition that makes halving legal. Search for 23 in indexes 0..9.

target
23
def binary_search(nums: list[int], target: int) -> int:    """Index of target in sorted nums, else -1. O(log n)."""    lo, hi = 0, len(nums) - 1    while lo <= hi:                      # range [lo, hi] still valid        mid = (lo + hi) // 2        if nums[mid] == target:            return mid        if nums[mid] < target:            lo = mid + 1                 # discard left half AND mid        else:            hi = mid - 1                 # discard right half AND mid    return -1
Time: O(log n)Space: O(1)

Edge cases

  • Empty array: loop never runs, returns −1.
  • Target smaller/larger than everything: range collapses cleanly.
  • Duplicates: returns SOME occurrence — first/last needs the bound variants.

Common mistakes

  • lo < hi with [lo, hi] bounds skips a final one-element check.
  • lo = mid (without +1) on a two-element range loops forever.
  • Using it on unsorted data — the invariant is meaningless there.

Lower bound / upper bound (first true)

Half-open [lo, hi): lo converges to the first index where the condition holds. Every boundary problem is this in costume.

Lower bound / upper bound (first true)
def lower_bound(nums: list[int], x: int) -> int:    """First index i with nums[i] >= x (== len if none). O(log n)."""    lo, hi = 0, len(nums)                # half-open [lo, hi)    while lo < hi:        mid = (lo + hi) // 2        if nums[mid] >= x:               # condition holds → answer ≤ mid            hi = mid        else:                            # too small → answer > mid            lo = mid + 1    return lodef upper_bound(nums: list[int], x: int) -> int:    """First index i with nums[i] > x. count(x) = upper - lower."""    lo, hi = 0, len(nums)    while lo < hi:        mid = (lo + hi) // 2        if nums[mid] > x:            hi = mid        else:            lo = mid + 1    return lo
Time: O(log n)Space: O(1)

Edge cases

  • x absent: lower_bound returns the insertion point — exactly 'search insert position'.
  • All elements < x: both return len(nums).
  • Occurrences of x: [lower, upper) — subtract for the count.

Common mistakes

  • Mixing the closed-range [lo, hi] template with the half-open one mid-function — pick ONE and rehearse it.
  • hi = mid − 1 in the half-open version, skipping a possible answer.

Search in a rotated sorted array

A rotation leaves at least one half of any [lo, hi] range perfectly sorted. Identify the sorted half; check if the target lies inside it; discard accordingly.

Search in a rotated sorted array
def search_rotated(nums: list[int], target: int) -> int:    """Search in a rotated ascending array (distinct values). O(log n)."""    lo, hi = 0, len(nums) - 1    while lo <= hi:        mid = (lo + hi) // 2        if nums[mid] == target:            return mid        if nums[lo] <= nums[mid]:            # left half is sorted            if nums[lo] <= target < nums[mid]:                hi = mid - 1                  # target inside sorted left            else:                lo = mid + 1        else:                                 # right half is sorted            if nums[mid] < target <= nums[hi]:                lo = mid + 1                  # target inside sorted right            else:                hi = mid - 1    return -1
Time: O(log n)Space: O(1)

Edge cases

  • No rotation at all — the left-sorted branch handles it throughout.
  • nums[lo] <= nums[mid] must use <= for the two-element case.
  • Duplicates break the sorted-half test — worst case degrades to O(n) (state this).

Common mistakes

  • Testing which half contains the target before establishing which half is SORTED — the checks only work inside the sorted half.
  • Using < instead of <= in the sorted-half test, misclassifying two-element ranges.

Binary search on the answer

When answers form a monotonic feasible/infeasible line, binary search candidate answers and run a feasibility check per probe.

Binary search on the answer
def min_capacity_to_ship(weights: list[int], days: int) -> int:    """Smallest ship capacity that ships all packages in <= days.    O(n log(sum)) — binary search over capacities, O(n) check each."""    def can_ship(capacity: int) -> bool:        used_days, load = 1, 0        for w in weights:            if load + w > capacity:                used_days += 1           # start a new day                load = 0            load += w        return used_days <= days    lo = max(weights)                    # must fit the heaviest package    hi = sum(weights)                    # one day ships everything    while lo < hi:                       # find FIRST feasible capacity        mid = (lo + hi) // 2        if can_ship(mid):            hi = mid                     # feasible → try smaller        else:            lo = mid + 1                 # infeasible → need bigger    return lo
Time: O(n · log(range of answers))Space: O(1)

Edge cases

  • lo must start at max(weights) — anything lower is infeasible by definition.
  • Feasibility must be MONOTONIC (bigger capacity never hurts) or the method is invalid — verify it out loud.
  • Answer range on values, not indexes: bounds come from the problem's physics.

Common mistakes

  • Binary searching answers without checking monotonicity first.
  • Returning mid instead of lo — the loop's post-condition is that lo == hi == first feasible.

Complexity analysis

OperationBestAverageWorstSpace
Linear searchO(1)O(n)O(n)O(1)
Binary search (sorted array)O(1)O(log n)O(log n)O(1)
Lower/upper boundO(log n)O(log n)O(log n)O(1)
Rotated-array search (distinct)O(1)O(log n)O(log n)O(1)
Binary search on answer—O(check · log range)O(check · log range)O(1)
Exponential search (unbounded)O(1)O(log i)O(log i)O(1)

i = position of the target in exponential search. Recursive binary search adds O(log n) stack for no benefit — write the loop.

Python implementation

Production-quality code with type hints, validation, and docstrings.

The reusable first-true template (one template, every variant)
from typing import Callabledef first_true(lo: int, hi: int, feasible: Callable[[int], bool]) -> int:    """Smallest x in [lo, hi] with feasible(x) True; hi+1 if none.    Requires feasibility to be monotonic: F,F,...,F,T,...,T.    """    hi += 1                              # half-open [lo, hi)    while lo < hi:        mid = (lo + hi) // 2        if feasible(mid):            hi = mid                     # keep mid as a candidate        else:            lo = mid + 1                 # mid is out; answer is right    return loif __name__ == "__main__":

What interviewers expect you to know

What interviewers expect you to know

  • The invariant discipline: say what [lo, hi] means and keep every branch consistent with it.
  • Bounds: lower_bound (first ≥) vs upper_bound (first >) and that count(x) = upper − lower.
  • The rotated-array insight: one half is always sorted.
  • The answer-space reframe: minimise/maximise + monotonic feasibility = binary search on the answer.

Classic follow-ups

  • "What if there are duplicates?" — first/last occurrence via bounds; rotated arrays degrade to O(n) worst case.
  • "Why doesn't (lo+hi)/2 overflow in Python?" — arbitrary-precision ints; in Java/C++ use lo + (hi−lo)/2 (worth saying you know).
  • "Prove termination" — the range shrinks by ≥ 1 every iteration because mid is always excluded from one side.

How to avoid the off-by-one trap live

  • Announce your convention before coding: 'closed range, lo <= hi, mid±1 both sides' — then never deviate mid-function.
  • Test the two-element range mentally; that's where infinite loops live.

Common mistakes

lo = mid without +1

On a two-element range, mid == lo; keeping mid in the range loops forever. Every branch must strictly shrink the range.

Mixing range conventions

Closed [lo, hi] pairs with lo <= hi and mid±1; half-open [lo, hi) pairs with lo < hi and hi = mid. Mixing halves of each is the #1 source of wrong answers.

Binary searching unsorted data

No sortedness (or monotonicity) = no legal discard. State the precondition; if input is unsorted, sort first (O(n log n)) or hash instead.

Feasibility that isn't monotonic

Binary-search-on-answer requires false…false,true…true. If feasibility can flicker, the discards are unsound — check before you search.

Returning mid from a bounds search

In the first-true template, the answer is lo AFTER the loop, not any mid you happened to probe.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (2)

Medium (8)

Hard (2)

Topic quiz

5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Complexity1. Maximum probes for binary search over 1,000,000 sorted elements?
  2. Code output2. lower_bound([1, 3, 3, 3, 7], 3) and upper_bound([1, 3, 3, 3, 7], 3) return…
  3. Concept3. In a rotated sorted array like [6,7,1,2,3,4,5], the key property enabling O(log n) search is…
  4. Scenario4. Koko must eat all banana piles within h hours; eating speed k is feasible iff total hours(k) ≤ h. Why does binary search on k work?
  5. Code output5. What's wrong with this loop?
    lo, hi = 0, len(nums) - 1while lo < hi:    mid = (lo + hi) // 2    if nums[mid] < target:        lo = mid    else:        hi = mid - 1
0 of 5 answered

Frequently asked questions

How do I stop making off-by-one errors in binary search?

Standardise on ONE template (the half-open first-true version is the safest), state the invariant in a comment, and mentally run the two-element case. Consistency beats cleverness here.

When is linear search actually the right answer?

Unsorted data you'll search once (sorting first costs more than scanning), tiny arrays, linked structures without random access, or when you need every match anyway.

How do I recognise 'binary search on the answer' problems?

The ask is 'minimum/maximum value such that …' and checking a candidate is easy, while finding it directly is hard. Confirm feasibility is monotonic, set honest lo/hi from the constraints, then first-true.

Summary & cheat sheet

Key takeaways

  • Binary search needs monotonic structure — sortedness is just its most common form.
  • One template (half-open, first-true) derives every variant safely.
  • Bounds: first ≥ and first > — their difference counts occurrences.
  • Rotated arrays: find the sorted half, test membership there, discard.
  • Min/max + easy monotonic check = binary search the answer space.

Formulas & cheat sheet

  • Probes ≤ ⌈log₂ n⌉ + 1
  • count(x) = upper_bound(x) − lower_bound(x)
  • last_false = first_true − 1
  • Overflow-safe mid (other languages): lo + (hi − lo) // 2

Interview checklist

  • I can write classic binary search and both bounds without hesitation.
  • I can explain and code the rotated-array search.
  • I can spot answer-space monotonicity and set honest lo/hi.
  • I test the two-element case before declaring done.