Binary Search Formula
The Formula
When to use: Looking up a word in a dictionary: open to the middle, then go left or right depending on where your word falls.
Quick Example
What This Formula Means
An efficient algorithm for finding a target value in a sorted list by repeatedly halving the search range. At each step, compare the target to the middle element: if equal, the search is done; if smaller, search the left half; if larger, search the right half.
Looking up a word in a dictionary: open to the middle, then go left or right depending on where your word falls.
Formal View
Common Mistakes
- Applying binary search to an unsorted list, which produces incorrect results
- Computing the midpoint as (low + high) / 2, which can cause integer overflow—use low + (high - low) / 2 instead
- Getting the boundary updates wrong (using mid instead of mid+1 or mid-1), causing infinite loops
Why This Formula Matters
Binary search is orders of magnitude faster than linear search for large sorted datasets. Searching 1 billion sorted items takes at most 30 comparisons with binary search, compared to up to 1 billion with linear search.
Frequently Asked Questions
What is the Binary Search formula?
An efficient algorithm for finding a target value in a sorted list by repeatedly halving the search range. At each step, compare the target to the middle element: if equal, the search is done; if smaller, search the left half; if larger, search the right half.
How do you use the Binary Search formula?
Looking up a word in a dictionary: open to the middle, then go left or right depending on where your word falls.
Why is the Binary Search formula important in CS Thinking?
Binary search is orders of magnitude faster than linear search for large sorted datasets. Searching 1 billion sorted items takes at most 30 comparisons with binary search, compared to up to 1 billion with linear search.
What do students get wrong about Binary Search?
Binary search only works on sorted data — applying it to unsorted data gives wrong results.
What should I learn before the Binary Search formula?
Before studying the Binary Search formula, you should understand: searching, array, efficiency.