How Binary Search works

Before you start

• Sorting

  Binary search only works on sorted input. That lesson covers what sorting costs.

  Open lesson

Why it matters

Database indexes, symbol tables, and version histories are kept in order so lookup does not require reading every entry. Ignoring that order wastes the structure built into the data. For [-1, 0, 3, 5, 9, 12, 15, 20], find target 15 at index 6 with logarithmic comparisons rather than a full scan.

Given nums sorted ascending and target, return the index of target or -1. You must run in O(log n).

Input

nums = [-1, 0, 3, 5, 9, 12, 15, 20], target = 15

Output

6

In [-1, 0, 3, 5, 9, 12, 15, 20], middle value 5 rules out the first four indexes for target 15, and 12 rules out two more. Each comparison drops a sorted half instead of a linear scan's up to eight checks.

Start with lo = 0 and hi = 7. The middle index 3 holds 5, below target 15, so indexes 0 through 3 are impossible and lo becomes 4. The next middle, index 5, holds 12, so lo becomes 6.

Now the middle index is 6 and nums[6] is 15. Using while lo <= hi keeps a one-value range searchable; updating to mid + 1 or mid - 1 removes the checked value and guarantees progress. Each comparison discards about half the remaining indexes.