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.

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

ALGORITHMS · 02 / BINARY SEARCH

The Vault.

Watch the explainer

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.

SOLVE IT YOURSELF

Solve it: binary search

This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement binary_search(arr, target) on a sorted array: return the index of target, or -1 if it is absent. Aim for O(log n) — halve the search window each step instead of scanning.

HINTS — 4 IDEAS

The array is sorted — that is the one rule that lets you throw half away each step.
Keep a window [lo, hi] and look at its middle.
Target bigger than the middle? the answer is in the right half; smaller? the left half — either way the window halves.
When the window is empty (lo > hi), the value is not present → return -1.

CPython · WebAssembly

▶ Watch it explained

Binary Search: Time and Space Complexity, From First Principles

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 / 99 Algorithms done

NextFind the Peak by Thirds: Ternary Search Next on the “Throw away half the answers” ladder · rung 2 of 2

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more

Algorithms →