Binary Search

Efficient search in sorted data — the O(log n) pattern

Knowledge0%

Learn & Drill

Fluency0%

Drill & Speed

Retention0%

Mastery & Review

Confidence0%

All modes

Practice

Free tier: read the explanation here. Upgrade to Pro for Drills, Speed challenges & Mastery badges.

Upgrade

Knowledge

Fluency

Retention

Knowledge Debt detected

You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.

Big-O Notation0%

Sorting Algorithms0%

Explanation

finds an element in a sorted array in O(log n) by repeatedly halving the .

The core algorithm:

python def binary_search(arr: list, target: int) -> int: lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid # found elif arr[mid] < target: lo = mid + 1 # target is in right half else: hi = mid - 1 # target is in left half return -1 # not found arr = [1, 3, 5, 7, 9, 11, 13] binary_search(arr, 7) # 3 (index)

Why O(log n): each step halves the search space. For 1,000,000 items, you need at most 20 comparisons.

Using Python's bisect module:

python import bisect arr = [1, 3, 5, 7, 9] idx = bisect.bisect_left(arr, 5) # 2 — leftmost valid insertion point idx = bisect.bisect_right(arr, 5) # 3 — rightmost

Generalisation — binary search on the answer:

python # Problem: find minimum speed such that all packages delivered in D days def min_speed(weights, D): def can_deliver(speed): days = 1 current = 0 for w in weights: if current + w > speed: days += 1 current = 0 current += w return days <= D lo, hi = max(weights), sum(weights) while lo < hi: mid = (lo + hi) // 2 if can_deliver(mid): hi = mid else: lo = mid + 1 return lo

Pattern: if you can ask "is X sufficient?" and the answer transitions from No to Yes at some threshold, binary search finds that threshold in O(log(range)).

Examples

Find first occurrence (left bisect)

bisect_left gives the first position where target could be inserted

import bisect

def find_first(arr: list, target: int) -> int:
    """Return index of first occurrence, or -1 if not found."""
    idx = bisect.bisect_left(arr, target)
    if idx < len(arr) and arr[idx] == target:
        return idx
    return -1

arr = [1, 2, 2, 2, 3, 4]
find_first(arr, 2)   # 1 (first 2 is at index 1)
find_first(arr, 5)   # -1

Search in rotated sorted array

Classic interview variant — binary search still works on rotated sorted arrays

def search_rotated(nums: list[int], target: int) -> int:
    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

search_rotated([4, 5, 6, 7, 0, 1, 2], 0)  # 4

How well did you understand this?

Next in Algorithms & Data Structures

Stack

Continue