Intuition First: The Dictionary Flip#
You'd never look up "serendipity" in a paper dictionary by reading from page 1. You flip to the middle, land on "M", and instantly throw away the entire first half of the book. Flip to the middle of what's left, land on "T" — too far — so you throw away the back half. Each flip halves the pages you still have to consider, so even a 1,000-page dictionary is conquered in about 10 flips.
Binary search is that flip, formalized. And it works for the exact same reason a dictionary does: the entries are sorted. Without sorting, "throw away half" would be meaningless — the word could be anywhere.
The Problem#
Given a sorted array of integers nums and a target integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log N) runtime complexity.
The Core Concept: Divide & Conquer#
Binary Search operates on a simple principle: since the array is already sorted, we can query the middle element.
- If the middle element matches our target, we are done!
- If the target is smaller than the middle element, the target must reside in the left half. We can discard the entire right half.
- If the target is larger than the middle element, the target must reside in the right half. We can discard the entire left half.
By halving our search space at each iteration, we locate the element in logarithmic time.
Code Implementation#
Here is the standard iterative version of Binary Search:
- Time Complexity: O(log N) as we halve the array size each step.
- Space Complexity: O(1) auxiliary space for pointers.
Interactive Lab: Binary Search#
Try setting custom values, modifying the search target, and stepping through the execution to watch pointers (low, high, mid) shift in real-time.
Key Takeaway#
Binary Search is extremely powerful. For a list of 4 billion items, it takes at most 32 operations to locate any item or determine its absence. The primary requirement is that the collection must be sorted.