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) time complexity

Ask yourself: Is the data sorted by the value you want, so each check of the middle can rule out half?

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.

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

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

Worked examples

Example 1

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

Answer

4 comparisons; mids 4,7,8,9

First step

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

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

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

medium
Trace binary search for target =4 in [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 in [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
  • 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.