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

O(log⁡n)O(\log n) time complexity

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

Find 37 in [1,5,12,23,37,49,56]: check middle (23), go right, check middle (49), go left, find 37.

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

Binary search on sorted array A[0..n−1]A[0..n-1] for target tt: set l=0,r=n−1l=0, r=n-1. While l≤rl \leq r, compute m=⌊(l+r)/2⌋m = \lfloor(l+r)/2\rfloor. If A[m]=tA[m]=t, return mm. If A[m]<tA[m]<t, set l=m+1l=m+1. Else set r=m−1r=m-1. Runs in O(log⁡n)O(\log n) time.

Worked Examples

Example 1

medium
Trace binary search for target =20=20 in [2,4,6,8,10,12,14,16,18,20][2,4,6,8,10,12,14,16,18,20] (indices 0-9). List the midpoints visited and the comparison count.

Answer

4 comparisons; mids 4,7,8,94\text{ comparisons; mids }4,7,8,9

First step

1
low=0, high=9, mid=4 (value 10). 20>1020 > 10, low=5.

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Unlock answer keys One Family plan — every worked solution, all subjects

Example 2

medium
Trace binary search for target =4=4 in [2,4,6,8,10,12,14,16,18,20][2,4,6,8,10,12,14,16,18,20] (indices 0-9). Midpoints and comparison count.

Example 3

medium
Trace binary search for target =1=1 in [1,3,5,7,9,11,13,15,17,19][1,3,5,7,9,11,13,15,17,19] (indices 0-9). Midpoints and comparison count.

Common Mistakes

  • Applying binary search to an unsorted list, which produces incorrect results - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
  • Computing the midpoint as (low + high) / 2, which can cause integer overflow—use low + (high - low) / 2 instead - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
  • Getting the boundary updates wrong (using mid instead of mid+1 or mid-1), causing infinite loops - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
  • Using binary search from a keyword alone - Signal words like algorithm, search, sort only point to a possible model; the computing structure must match too.

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.

← Back to Binary Search See All Examples Practice Problems

Related Formulas

Linear Search Formula