Binary Search Formula
Binary search is an efficient algorithm for finding a target value in a sorted list by repeatedly halving the search range.
The Formula
Ask yourself: Is the data sorted by the value you want, so each check of the middle can rule out half?
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.
Binary search is how you find page 412 in a thick book: open near the middle, see whether the page number there is too high or too low, and keep only the half that must contain 412. It works because page numbers are in order; if the pages were shuffled, the number you opened to would tell you nothing.
Formal view
Worked examples
Example 1
mediumShow solution
Answer
First step
See the full worked solution + why-it-works coaching
SetupKey insightWhy it worksCommon pitfallConnection
Example 2
mediumExample 3
mediumCommon mistakes
- Applying binary search to an unsorted list, which produces incorrect results
- Computing the midpoint as (low + high) / 2, which can cause integer overflow in languages with fixed-size integers, such as Java or C—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 why looking something up in a huge sorted index feels instant: doubling the data adds just one comparison. It is also famously easy to get subtly wrong. Writing high = mid instead of mid − 1 can loop forever, a missing low ≤ high check runs off the list, and on unsorted data it reports 'not found' for values that are there.
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?
Use binary search when the collection is sorted by the value you are looking for and you can jump straight to any position by index, as in an array. It also fits any guess-and-narrow problem where each check answers higher or lower, such as finding the first version of a program that contains a bug. If the data is unsorted, or is a chain you must walk item by item, use linear search. For a tiny list, linear search is just as good.
Why is the Binary Search formula important in CS Thinking?
Binary search is why looking something up in a huge sorted index feels instant: doubling the data adds just one comparison. It is also famously easy to get subtly wrong. Writing high = mid instead of mid − 1 can loop forever, a missing low ≤ high check runs off the list, and on unsorted data it reports 'not found' for values that are there.
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.