beginnerintermediateadvanced

Data Structures & Algorithms · Section 10

Searching and Binary Search

Level: beginner
Read: 85 min
Concepts: 10

Linear search as the O(n) baseline, binary search as the O(log n) replacement once data is sorted — the loop invariant that keeps it off-by-one-free, leftmost/rightmost occurrence, binary search on the answer, rotated arrays, 2D matrices, and the bisect module that replaces hand-rolling most of it.

What is true here

Binary search needs sorted input and gives a silently wrong answer, not an error, if that precondition is violated.
The loop invariant "target, if present, is in nums[lo..hi]" is what while lo <= hi and mid + 1 / mid - 1 protect.
Binary search on the answer applies the same halving to any monotonic yes/no condition, with no literal array involved.
bisect_left / bisect_right / insort cover plain sorted-list lookups and inserts — write a custom loop only when there is no real sorted sequence to search, or the comparison is not plain less-than.

What you will be able to do

Write a binary search whose loop condition and boundary updates are provably free of the classic off-by-one bug
Recognize "minimum/maximum X such that a condition holds" as binary search on the answer, not on an array
Adapt binary search to a rotated sorted array or a fully sorted 2D matrix
Choose bisect over a hand-written loop whenever a real sorted sequence is actually being searched

Concepts

From a linear scan to halving a sorted range, the invariant that keeps it correct, and the shapes binary search takes beyond a plain array.

Linear search — O(n)

referencebeginner

Linear search checks every element in order until it finds the target or runs out of elements — O(n), and the only option when the data is not sorted.

What we're doing: Find the index of a target value by checking each element in order.

linear_search.pypython

def linear_search(nums, target):
    for i, n in enumerate(nums):
        if n == target:
            return i
    return -1


print(linear_search([4, 2, 9, 7, 1], 7))
print(linear_search([4, 2, 9, 7, 1], 5))

3: Every element is compared, in order — there is no way to skip ahead without knowing the data is sorted.
4: The function returns the moment it finds a match; it never needs to look at the rest.

Output

3
-1

Why this works: 7 sits at index 3, so the loop returns as soon as it gets there. 5 never appears, so the loop runs to the end and returns -1.

Remember: Reach for linear search when the data is not sorted, or when you will only search it once — binary search only pays off once the data is sorted and searched repeatedly.

Binary search on a sorted array — O(log n)

corebeginner

On a sorted array, compare the target to the middle element and throw away the half it cannot be in. Repeating that halves the search space every step, giving O(log n) instead of O(n).

Think of it as

Think of it like looking up a name in a phone book: open to the middle, decide whether the name is before or after that page, and throw away the half you just ruled out. Each comparison eliminates half of what is left, so n items take only about log2(n) comparisons.

What we're doing: Find the index of a target value in a sorted list, or -1 if it is absent.

binary_search.pypython

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


print(binary_search([1, 3, 5, 7, 9, 11], 7))
print(binary_search([1, 3, 5, 7, 9, 11], 4))

3: lo <= hi means the search space still has at least one candidate index in it.
6: target is bigger than the middle value, so it can only be to the right — the left half, including mid, is discarded.
8: target is smaller than the middle value, so the right half, including mid, is discarded.

Output

3
-1

Why this works: 7 sits at index 3 in [1, 3, 5, 7, 9, 11], so the loop lands on it directly. 4 does not appear in the list at all, so lo eventually passes hi and the loop returns -1.

Running binary search on data that is not actually sorted

Wrong

python

unsorted = [5, 1, 9, 3, 7]
print(binary_search(unsorted, 3))

Better

python

sorted_once = sorted(unsorted)
print(binary_search(sorted_once, 3))

What you see: 3 is at index 3 in [5, 1, 9, 3, 7] (confirmed by unsorted.index(3)), but binary_search(unsorted, 3) returns -1 — claiming 3 is not there at all.

Why: Binary search decides which half to discard by comparing target to the middle element and trusting that everything smaller is to the left and everything larger is to the right. On unsorted data that assumption is false, so it can discard the half that actually contains the target — silently, with no exception raised.

Binary SearcheasyLeetCode
Exactly the example above — halve the search space until the target is found or the space is empty.
First Bad VersioneasyLeetCode
The same loop, but the array is implicit — isBadVersion(mid) plays the role of the comparison against nums[mid].

Remember: Binary search only works on sorted data — it never checks that precondition itself, so passing unsorted data gives a wrong answer with no error.

Was this helpful?

Writing binary search without off-by-one bugs (lo, hi, mid, loop invariant)

corebeginner

The invariant is: "if the target exists, it is somewhere in nums[lo..hi]". Every line has to protect that invariant — the loop condition, and both branches that move lo or hi.

Think of it as

Treat [lo, hi] as the set of indices still under suspicion. The loop must keep running as long as that set is non-empty (lo <= hi, not lo < hi), and each branch must exclude mid once it has been ruled out (mid + 1 or mid - 1, never mid itself) — otherwise an index can get silently dropped from the search space without ever being checked.

What we're doing: Show why the loop condition has to be lo <= hi, using a target that is the very last candidate standing.

off_by_one.pypython

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 9))

3: lo <= hi is required so the single-candidate case (lo == hi) still runs one more comparison instead of being skipped.

Output

Why this works: On [1, 3, 5, 7, 9] searching for 9, lo climbs to 4 and hi is already 4 — exactly one candidate is left, at index 4. Because the loop condition is lo <= hi, that last candidate still gets checked, and it is the target.

Using `while lo < hi` instead of `while lo <= hi`

Wrong

python

def binary_search_wrong(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


print(binary_search_wrong([1, 3, 5, 7, 9], 9))

Better

python

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

What you see: binary_search_wrong([1, 3, 5, 7, 9], 9) returns -1, even though 9 is in the list at index 4.

Why: By the time lo and hi both equal 4, the target has not been found yet, and lo < hi (4 < 4) is False — the loop exits without ever comparing nums[4] to the target. The single remaining candidate is dropped from the search instead of being checked.

Search Insert PositioneasyLeetCode
A correct lo <= hi binary search naturally lands lo on the insertion point when the target is absent — no special-casing needed.
Guess Number Higher or LowereasyLeetCode
Same invariant, with guess(mid) standing in for the comparison against a real array element.

Remember: The invariant is "the target, if present, is in nums[lo..hi]" — while lo <= hi keeps a single remaining candidate in play, and mid + 1 / mid - 1 keep a ruled-out mid from ever coming back.

Was this helpful?

Binary search for exact match vs "leftmost/rightmost occurrence"

standardbeginner

On a sorted array with duplicates, plain binary search returns SOME index holding the target — not necessarily the first or last one. Finding a specific boundary needs a small change: keep narrowing even after a match, instead of returning immediately.

Think of it as

Plain binary search stops at the first match it happens to land on, which can be anywhere among duplicates. To find the leftmost one, keep searching the left half even after a match, recording the best index found so far — and mirror that to the right for rightmost.

What we're doing: Compare a plain binary search against dedicated leftmost/rightmost searches on an array with repeated values.

leftmost_rightmost.pypython

def find_leftmost(nums, target):
    lo, hi = 0, len(nums) - 1
    result = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            result = mid
            hi = mid - 1
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result


def find_rightmost(nums, target):
    lo, hi = 0, len(nums) - 1
    result = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            result = mid
            lo = mid + 1
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result


arr = [1, 2, 2, 2, 3]
print(find_leftmost(arr, 2))
print(find_rightmost(arr, 2))

4: result is only recorded, not returned — the search keeps going to see if an earlier match exists.
5: hi = mid - 1 (not lo = mid + 1) discards the right half, including this match, forcing the search left.
14: find_rightmost is the exact mirror image: record the match, then push lo past it to search right.
15: lo = mid + 1 discards the left half, including this match, forcing the search right.

Output

1
3

Why this works: The 2s in [1, 2, 2, 2, 3] occupy indices 1, 2, and 3. find_leftmost keeps narrowing left on every match and settles on index 1; find_rightmost keeps narrowing right and settles on index 3.

Find First and Last Position of Element in Sorted ArraymediumLeetCode
Exactly find_leftmost and find_rightmost from the example above, run back to back on the same array.
Search Insert PositioneasyLeetCode
find_leftmost applied to a target that may not be present — the loop naturally settles on the insertion point.

Remember: A match is not automatically the answer when duplicates exist — record it, then keep narrowing in the direction (left for leftmost, right for rightmost) that could still improve it.

Was this helpful?

Binary search on the answer

corebeginner

Binary search does not need a literal array — it works on any range of candidate answers where a yes/no condition flips exactly once from false to true. Search that range instead of the input.

Think of it as

Ask "if the answer were X, would that work?" for a candidate X. If the answer is monotonic — every value below some threshold fails and every value at or above it works — that yes/no result is exactly what nums[mid] < target was doing in ordinary binary search. lo and hi now bound the space of possible answers, not array indices.

What we're doing: Compute floor(sqrt(n)) without **, by binary searching the range of integers 0..n for the largest x with x*x <= n.

int_sqrt.pypython

def int_sqrt(n):
    lo, hi = 0, n
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans


print(int_sqrt(15))
print(int_sqrt(16))
print(int_sqrt(1))
print(int_sqrt(0))

4: lo and hi bound the range of CANDIDATE ANSWERS (0 through n), not indices into an array — there is no array here at all.
5: mid * mid <= n is the monotonic condition: true for every integer up to floor(sqrt(n)), false for every integer beyond it.
6: ans is saved before pushing lo past mid, exactly like tracking "leftmost/rightmost" — the last value where the condition held is the answer.

Output

Why this works: 15 is between 3*3=9 and 4*4=16, so the largest x with x*x <= 15 is 3. 16 is itself a perfect square, so the answer is exactly 4.

Using a strict `<` instead of `<=` in the monotonic condition

Wrong

python

def int_sqrt_wrong(n):
    lo, hi = 0, n
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid < n:
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans


print(int_sqrt_wrong(16))
print(int_sqrt_wrong(25))

Better

python

def int_sqrt(n):
    lo, hi = 0, n
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

What you see: int_sqrt_wrong(16) returns 3 and int_sqrt_wrong(25) returns 4 — undershooting by exactly 1 whenever n is itself a perfect square.

Why: The condition mid * mid < n excludes mid == sqrt(n) itself, since a perfect square makes mid * mid equal to n, not less than it. The candidate that is actually the true answer never gets accepted, so the search settles one step short of it.

Arranging CoinseasyLeetCode
Binary search the largest k over [0, n] such that k * (k + 1) // 2 <= n — the same shape as int_sqrt above, just a different monotonic condition.
Koko Eating BananasmediumLeetCode
Binary search eating speed k over [1, max(piles)] — "can Koko finish at speed k within h hours?" is monotonic in k.

Remember: Whenever a problem asks for the minimum/maximum value satisfying a yes/no condition that flips exactly once, binary search the range of possible answers — get the boundary condition (<= vs <) exactly right, since it decides whether the true answer itself is accepted.

Was this helpful?

Binary search on a rotated sorted array

corebeginner

A rotated sorted array is still sorted in two pieces. At any mid, one of the two halves (nums[lo..mid] or nums[mid..hi]) is guaranteed to be in normal sorted order — check that half first.

Think of it as

Pick a mid. Compare nums[lo] to nums[mid]: whichever side is not "broken" by the rotation point is a normal sorted range, so a normal check (is target within its low/high bounds?) tells you whether to search there — otherwise the target must be in the other, still-rotated half, and you recurse into that one instead.

What we're doing: Find a target in a sorted array that has been rotated at an unknown pivot.

search_rotated.pypython

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


arr = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(arr, 0))
print(search_rotated(arr, 3))

7: nums[lo] <= nums[mid] means no rotation point falls inside [lo, mid] — that half is normally sorted.
8: Because the left half is normal, an ordinary range check (nums[lo] <= target < nums[mid]) decides whether target is in it.

Output

4
-1

Why this works: [4, 5, 6, 7, 0, 1, 2] is [4, 5, 6, 7] rotated with [0, 1, 2]. 0 sits at index 4. 3 does not appear anywhere in the array, so the search exhausts lo/hi and returns -1.

Using `<` instead of `<=` when checking which half is sorted

Wrong

python

def search_rotated_wrong(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] < nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


print(search_rotated_wrong([3, 1], 1))

Better

python

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

What you see: search_rotated_wrong([3, 1], 1) returns -1, even though 1 is in the array at index 1.

Why: When lo == mid (a single-element left half), nums[lo] < nums[mid] compares a value to itself and is False, so the code wrongly treats the RIGHT half as the sorted one. That misclassifies a one-element left half that trivially satisfies nums[lo] <= nums[mid] (equal, not less), and target gets searched on the wrong side.

Peak Index in a Mountain ArrayeasyLeetCode
Same instinct as the rotation-point check above — comparing nums[mid] to a neighbor tells you which half to discard, without a plain sorted array.
Search in Rotated Sorted ArraymediumLeetCode
Exactly the example above — decide which half is normally sorted, then check target against that half's bounds.

Remember: Use nums[lo] <= nums[mid] (not strict <) to decide which half is sorted — a one-element left half has nums[lo] == nums[mid], and it is still trivially sorted.

Was this helpful?

Search in a 2D sorted matrix

standardbeginner

When a matrix is sorted along every row and every column, it can be treated as one long sorted list of rows * cols elements — binary search it directly using index math to convert between a flat position and a (row, col) pair.

Think of it as

A flat index mid maps to row = mid // cols, col = mid % cols. Reading the matrix that way, row by row, gives exactly the same non-decreasing sequence a 1D binary search expects — so the ordinary lo/hi/mid loop works unchanged, only the "read the value" step changes.

What we're doing: Search a fully sorted matrix as if it were one flat sorted list.

search_matrix.pypython

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


matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60],
]
print(search_matrix(matrix, 16))
print(search_matrix(matrix, 13))

4: lo and hi bound a flat index from 0 to rows * cols - 1, exactly like a 1D array of that length.
5: mid // cols and mid % cols turn the flat index back into the row and column to actually read.

Output

(1, 2)
None

Why this works: 16 sits at row 1, column 2 (flat index 6). 13 does not appear anywhere in the matrix, so the search exhausts lo/hi and returns None.

Remember: A fully sorted matrix is one sorted list in disguise — binary search it with mid // cols and mid % cols standing in for the row and column.

Python tools

The standard-library module built specifically for searching and maintaining sorted sequences.

`bisect.bisect_left` / `bisect.bisect_right`

standardbeginner

bisect_left finds the leftmost position where a value could be inserted and keep the list sorted; bisect_right finds the rightmost such position. The gap between them is exactly the count of that value in the list.

Think of it as

Both answer "where would this value go to keep the list sorted?" — bisect_left picks the earliest valid slot (before any equal elements), bisect_right picks the latest one (after any equal elements). On a list with no duplicates of the target, they return the same index.

What we're doing: Find the leftmost and rightmost insertion points for a duplicated value, and use their gap to count occurrences.

bisect_left_right.pypython

import bisect

arr = [1, 2, 2, 2, 3]
print(bisect.bisect_left(arr, 2))
print(bisect.bisect_right(arr, 2))
print(bisect.bisect_right(arr, 2) - bisect.bisect_left(arr, 2))
print(bisect.bisect_left(arr, 5))

3: bisect_left(arr, 2) is 1 — the first 2 starts at index 1, and inserting a new 2 there keeps all existing 2s to its right.
4: bisect_right(arr, 2) is 4 — one past the last 2, so inserting a new 2 there keeps all existing 2s to its left.

Output

Why this works: The three 2s occupy indices 1-3, so bisect_left lands at 1 and bisect_right lands at 4, a gap of 3 — matching the actual count of 2s. 5 is larger than every element, so both would insert it at the end, index 5.

Find First and Last Position of Element in Sorted ArraymediumLeetCode
bisect_left(nums, target) and bisect_right(nums, target) - 1 give the first and last position directly, if the target is present at all.
Search Insert PositioneasyLeetCode
bisect_left(nums, target) IS the answer — the leftmost valid insertion point is exactly where the target belongs.

Remember: bisect_left is the leftmost valid insertion point, bisect_right is the rightmost — reach for the gap between them whenever you need to count a value in a sorted list.

Was this helpful?

bisect.insort for maintaining a sorted list

standardbeginner

bisect.insort finds the correct sorted position for a value and inserts it there in one call, so the list never needs a full re-sort after adding an element.

Think of it as

insort is bisect_left (or bisect_right) followed by list.insert at that position — it finds where the value belongs in O(log n), then shifts everything after it over by one to make room. That shift is still O(n), so insort is not a free O(log n) insert; it only skips the O(n log n) of re-sorting the whole list.

What we're doing: Build a sorted list one element at a time, using insort instead of appending and re-sorting.

bisect_insort.pypython

import bisect

sorted_list = []
for n in [5, 1, 9, 3]:
    bisect.insort(sorted_list, n)
    print(sorted_list)

4: insort finds the correct position for n and inserts it there directly — the list is sorted again immediately, with no separate sort step.

Output

[5]
[1, 5]
[1, 5, 9]
[1, 3, 5, 9]

Why this works: Each call places its value exactly where sorted order requires: 1 goes before 5, 9 goes after 5, and 3 goes between 1 and 5 — the list is sorted after every single insertion, not just at the end.

Remember: insort keeps a list sorted after every insert, in O(n) per call — cheaper than re-sorting from scratch, but still not O(log n), because shifting elements to make room is unavoidable in a plain list.

Was this helpful?

Knowing when bisect is enough vs when you must write custom binary search

referencebeginner

bisect only ever answers "where does this value belong in this real, already-sorted list?" — the moment there is no literal sorted list to hand it, write the lo/hi/mid loop yourself.

Remember: If there is a real sorted sequence to search, reach for bisect first. If the "array" is actually a range of possible answers, or the comparison is not plain less-than, write the binary search by hand.

Was this helpful?

Spotted a mistake on this page? Tell us.

Read Sheet