What is the difference between binary search and linear search?

Linear search checks every element one by one and works on any array in O(n) time. Binary search needs a sorted array but only checks about log2(n) elements, making it dramatically faster on large datasets. Linear search wins only for tiny or unsorted arrays.

How do you avoid integer overflow when computing the midpoint?

Use mid = low + (high - low) / 2 instead of (low + high) / 2. In fixed-width integer languages, low + high can overflow when both are large; subtracting first avoids it. This is a classic, real binary-search bug that shipped in production libraries for years.

ALGORITHMS · 02 / BINARY SEARCH

The Vault.

Q: What is binary search?

Binary search is an algorithm that finds the position of a target value in a sorted array by repeatedly halving the search range. It compares the target to the middle element and discards the half that cannot contain it, so it finds any value in O(log n) time instead of scanning every element.

Q: What is the time complexity of binary search?

Binary search runs in O(log n) time, because each comparison eliminates half of the remaining elements. For an array of 1,000,000 items it needs at most about 20 comparisons. Space is O(1) for the iterative version and O(log n) for the recursive version (call stack).

Q: Why does binary search require a sorted array?

Binary search works by deciding which half to discard from a single comparison with the middle element. That decision is only valid if the data is ordered: if the array is unsorted, 'the target is smaller than the middle' tells you nothing about where it is, so you cannot safely throw away half. On unsorted data you must use linear search or sort first.

Q: Where is binary search used in real life?

Database and search-engine indexes, the 'git bisect' command for finding the commit that broke a build, autocomplete and dictionary lookups, finding insertion points in sorted collections, and 'binary search on the answer' for optimization problems.

A vault of sorted dials hides one number. You'll crack it by instinct and burn through guesses — then meet the Halver, who throws away half the vault with every single look.

THE GIST · 20 SECONDS

Binary search finds a value in a sorted list by checking the middle and throwing away the half that can't contain it — then repeating on what's left. Each look halves the problem, so it finds anything in O(log n) steps: ~20 looks for a million items. It's how databases, dictionaries and git bisect find things fast.

Sortedelements in order — the precondition
low / highthe current search window
midthe middle index you check
Halvingdiscard half each comparison → O(log n)

① Crack it blind → ② Meet the Halver → ③ Predict the midpoint

Find: —

UNDER THE HOOD

What you just played, written down

You cracked it, watched the window collapse, and predicted the midpoint. Here's the same thing as code.

How the Halver thinks — four steps

Set the window. low = first index, high = last index.
Look at the middle. mid = low + (high − low) / 2. Compare it to the target.
Throw away a half. If the middle is too small, move low past it; if too big, move high before it.
Repeat until you land on the target or the window is empty (not found).

WHY IT'S FAST

Every comparison deletes half the remaining dials. Halving a million takes only ~20 steps — that's what O(log n) means, and why it crushes checking one-by-one.

The algorithm

function binarySearch(arr, target):
    low = 0
    high = arr.length - 1
    while low <= high:
        mid = low + (high - low) / 2   # avoids overflow
        if arr[mid] == target:
            return mid                 # found
        else if arr[mid] < target:
            low = mid + 1              # discard left half
        else:
            high = mid - 1            # discard right half
    return -1                          # not present

TIMEO(log n)halves the range each step

SPACEO(1)iterative · O(log n) recursive

Solved by hand — the exact trace for the vault above

Each look, with the window it searched and the decision it made.

⚠ It needs sorted data

Binary search only works on a sorted array — the whole "throw away a half" trick relies on order. On unsorted data, use linear search or sort first.

↔ Its cousins

Linear search is O(n) but needs no order. Interpolation search guesses the position from the value (O(log log n) on uniform data). "Binary search on the answer" solves optimization problems.

★ Where you've used it

Database indexes, git bisect, dictionary & autocomplete lookups, and finding the insertion point in any sorted collection.

QUICK CHECK

Did it stick?

FAQ

Binary search, answered

What is binary search?

Binary search finds a value in a sorted array by repeatedly checking the middle and discarding the half that can't contain the target. It finds anything in O(log n) instead of scanning every element.

What is the time complexity of binary search?

O(log n) — each comparison eliminates half the elements, so a million items need at most ~20 looks. Space is O(1) iterative, O(log n) recursive.

Why does binary search require a sorted array?

The "discard a half" decision is only valid if the data is ordered. On unsorted data, "smaller than the middle" tells you nothing about where the target is, so you can't safely throw anything away.

Binary search vs linear search?

Linear search checks every element (O(n)) but works on any array. Binary search needs sorted data but only checks ~log₂(n) elements — far faster at scale.

How do you avoid the midpoint overflow bug?

Use mid = low + (high - low) / 2 instead of (low + high) / 2. The naive form can overflow fixed-width integers — a real bug that shipped in production libraries for years.

Where is binary search used in real life?

Database indexes, git bisect, dictionary & autocomplete lookups, sorted-collection inserts, and "binary search on the answer" for optimization.

Finished this one? 0 / 5 Algorithms done

More Algorithms

Explore more from Vibe Engines

Handbooks →

Roadmaps →

Prompt Engineering Roadmap

System Designs →

AI System Designs →

Labs →

Gradient Descent: The Descent