On this concept: Formula

Not sure which lesson to do first? Find your level and get a plan →

CS Thinking · Computational Thinking · Grade 9-12

Binary Search

An efficient algorithm for finding a target value in a sorted list by repeatedly halving the search range.

O(log⁡n) time complexity

Quick Answer

An efficient algorithm for finding a target value in a sorted list by repeatedly halving the search range. You keep two indexes, low and high, look at the middle element, and move low to mid + 1 or high to mid − 1 depending on whether the target is larger or smaller. When low passes high, the target is not there. Use it whenever the data is sorted by the value you want: a sorted list of a billion items needs at most 30 comparisons.

Why This 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.

Intuitive Explanation

Take the sorted list [4, 9, 15, 22, 30, 41, 56, 63, 78], indexes 0 to 8, and look for 56. Set low = 0 and high = 8. The middle index is (0 + 8) // 2 = 4, holding 30. Since 56 > 30, the target can only be to the right, so low = 5. Now mid = (5 + 8) // 2 = 6, holding 56: found in 2 comparisons. Each comparison discards everything on one side of mid, plus mid itself.

That 'plus mid itself' matters. After checking a[mid], the new range must leave it out: low = mid + 1 or high = mid − 1. Write low = mid instead and a range of two items can stay the same size forever. The loop runs while low ≤ high; once low is greater than high, the range is empty and the answer is 'not found'. Search the same list for 50: mid 4 holds 30, go right, low = 5; mid 6 holds 56, go left, high = 5; mid 5 holds 41, go right, low = 6. Now low = 6 > high = 5, so 50 is not in the list.

Because the range halves each time, a list of n items needs at most ⌊log⁡2n⌋+1 comparisons: 4 for 9 items, 10 for 1,000, 30 for a billion. The catch is that the list must be sorted by the same value you search for. A class list sorted by name can be binary-searched for a name, but not for a test score; finding who scored 88 needs linear search or a second list sorted by score.

Think of it like this. 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.

Core idea. Each comparison eliminates half the remaining possibilities — O(log n) vs O(n) for linear search.


When to Use

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.

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

How to Recognize It

Before choosing binary search, check that the data's order lets one comparison tell you which half to discard.

  1. Is the collection already sorted by the very value you are looking for?

    Yes allows binary search. A list of students sorted by name cannot be binary-searched for a test score; with no usable order you need Linear Search.

  2. Can you jump straight to the middle item, as with an array index?

    Yes means each step costs one look. On a linked chain that must be walked from the front, reaching the middle costs as much as a Linear Search, so the speed-up disappears.

  3. After each comparison, is one half thrown away and never looked at again?

    Yes is binary search. If both halves are solved and their answers combined, as in Merge Sort, the method is the wider Divide and Conquer.

  4. Will the same sorted list be searched many times?

    Yes makes binary search pay off, even counting one sort at the start. For a single search of an unsorted list, sorting first costs more than one Linear Search.

Binary Search vs Linear Search vs Divide and Conquer vs Binary

Binary search shares its name with base-2 numbers and its halving with divide and conquer, and it competes with linear search for the same job. Ask what order the data has and what happens to the half you do not keep.

Binary Search

Meaning
Binary search finds a target in sorted data by checking the middle item and keeping only the half that could contain it.
Key test
Sorted data, one middle check per step, half discarded each time.
Formula
⌈log⁡2(n+1)⌉ checks at most
Example
Finding 42 in a sorted list of 1,000 numbers takes at most 10 checks.

Linear Search

Meaning
Linear search walks through the items from the first one onward until the target turns up or the list runs out.
Key test
Works on any order; the worst case looks at every item.
Formula
at most n checks
Example
Finding a phone number on an unsorted contact list of 1,000 names can take all 1,000 checks.

Divide and Conquer

Meaning
Divide and conquer splits a problem into smaller problems of the same kind, solves them all, and combines the results.
Key test
Every part is solved and the answers joined; binary search keeps only one part.
Formula
T(n)=aT(n/b)+f(n)
Example
Merge sort sorts both halves of a list and then merges them into one sorted list.

Binary

Meaning
Binary is the base-2 number system, which writes every value using only the digits 0 and 1.
Key test
The question is about digits and place values, not about finding an item.
Formula
1012=4+0+1=5
Example
Writing 12 in base 2 as 1100.

Formula & Notation

O(log⁡n) time complexity
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 — Trace low, high and mid

Easy

Use binary search to find 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indexes 0 to 9). Show low, high and mid at each step and count the comparisons.
Show the steps and the answer
  1. low = 0, high = 9, mid = (0 + 9) // 2 = 4, a[4] = 16. Since 23 > 16, set low = 5.

    Everything at index 4 or below is at most 16, so the target can only be at index 5 or above.

  2. mid = (5 + 9) // 2 = 7, a[7] = 56. Since 23 < 56, set high = 6.

    The target is smaller than 56, so it must lie left of index 7, and index 7 itself is excluded.

  3. mid = (5 + 6) // 2 = 5, a[5] = 23. Found.

    The range shrank from 10 items to 5, then to 2, before the match.

  4. Count: 3 comparisons. The worst case for 10 items is ⌊log⁡210⌋+1=4; linear search would need 6 to reach index 5.

    Comparing with the worst case and with linear search shows what the halving bought.

Answer: 23 is at index 5, found in 3 comparisons.

Takeaway: Track low, high and mid on every step, and make sure each step shrinks the range.

Example 2 — A match, but not the first one

Standard

In the sorted list [3, 7, 7, 7, 7, 9, 12] (indexes 0 to 6), standard binary search for 7 returns index 3. A program needs the first position of 7. Why does the standard version not give it, and how can binary search be changed to find it?
Show the steps and the answer
  1. Trace the standard search: mid = (0 + 6) // 2 = 3, a[3] = 7, return 3.

    Standard binary search stops at whichever 7 the middle happens to land on.

  2. Change one rule: when a[mid] equals the target, record mid as the best answer so far and keep searching left with high = mid − 1.

    Any earlier 7 must be to the left, so the left half is the only place a better answer can be.

  3. Continue: low = 0, high = 2, mid = 1, a[1] = 7, so record 1 and set high = 0. Then mid = 0, a[0] = 3 < 7, so low = 1.

    The search keeps halving, so it still takes O(log⁡n) steps.

  4. Now low = 1 > high = 0, so stop and return the recorded answer, 1.

    The empty range shows that no 7 exists before index 1.

Answer: The standard search returns index 3, an arbitrary 7. Recording each match and continuing left finds the first 7 at index 1, after 3 checks of the middle element (indexes 3, 1 and 0).

Takeaway: Binary search finds a match, not necessarily the first. To find the first, keep searching left after every match.

Example 3 — Find the mistake: low = mid never finishes

Application

Noah writes: while low <= high: mid = (low + high) // 2; if a[mid] == target, return mid; if a[mid] < target, low = mid; otherwise high = mid. Searching [10, 20, 30, 40] for 35, the program never finishes. Noah says: "Setting low = mid is fine, since mid was already checked." Find the mistake and correct it.
Show the steps and the answer
  1. Trace: low = 0, high = 3, mid = 1, a[1] = 20 < 35, so low = 1. Then mid = (1 + 3) // 2 = 2, a[2] = 30 < 35, so low = 2.

    So far the range is shrinking, so the bug has not shown itself yet.

  2. Next: mid = (2 + 3) // 2 = 2 again, a[2] = 30 < 35, so low = 2 again. Nothing changes.

    With low = mid, a two-item range keeps producing the same mid, so the loop repeats one step forever.

  3. Spot the flaw in Noah's reasoning: mid was checked, so it should be excluded, but low = mid keeps it in the range.

    Every update must remove mid; that is what guarantees the range gets smaller each time.

  4. Fix: low = mid + 1 and high = mid − 1. Re-trace: mid 1 (20), low = 2; mid 2 (30), low = 3; mid 3 (40 > 35), high = 2. Now low = 3 > high = 2: not found.

    The search now ends after 3 comparisons with the right result, since 35 is not in the list.

Answer: Use low = mid + 1 and high = mid − 1. The search for 35 then stops after 3 comparisons and reports 'not found'.

Takeaway: After checking a[mid], move past it. An update that keeps mid in the range can stop the range from shrinking.

Where You'll See It

  • Looking up a word in a dictionary

    You open near the middle, see whether your word falls before or after, and discard the other half, halving the pages to check each time exactly like binary search.

  • Guess-the-number game (1 to 100)

    The smart strategy is to guess 50, then use 'higher' or 'lower' to halve the range each guess, finding any number in at most 7 guesses, which is log⁡2(100) rounded up.

  • Finding a level on a sorted video list

    Because levels are numbered in order, an app can jump to the middle and decide which half holds level 73, reaching it in a handful of steps instead of scanning all levels.

Common Mistakes

  1. The slip: Binary search works on any list because it just checks the middle.

    Why it's tempting: The middle-check rule sounds like it works regardless of order.

    Instead: Binary search only works on sorted data. On an unsorted list, 'go left or right' is meaningless and the result is wrong.

  2. The slip: Computing the midpoint as (low + high) / 2 is always safe.

    Why it's tempting: It's the obvious average formula and works for small numbers.

    Instead: For very large indices, low + high can overflow in languages with fixed-size integers, such as Java or C (Python integers never overflow); compute the midpoint as low + (high - low) / 2 to stay safe.

  3. The slip: After comparing, I can set the new boundary to mid each time.

    Why it's tempting: Mid is the spot you just looked at, so reusing it seems natural.

    Instead: Move past the checked element: search left as high = mid - 1, or right as low = mid + 1. Reusing mid can loop forever because the range never shrinks.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Binary search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], indexes 0 to 9, with mid = (low + high) // 2. Which mid indexes are checked?

    Hint: Start with low = 0 and high = 9. Compare the target with the middle value each time.

  2. Binary search for 40 in [10, 20, 30, 50, 60], indexes 0 to 4. Trace low, high and mid until the search stops. What is the result?

    Hint: The search ends when low becomes greater than high.

  3. In the worst case, how many comparisons does binary search need for 1,000 sorted items? For 1,000,000?

    Hint: Find the smallest power of 2 that is at least the list size.

  4. A sorted list grows from 500 to 1,000 items. How many extra worst-case comparisons does binary search need? How many does linear search need?

    Hint: Work out the worst case for each list size, then subtract.

  5. You need one phone number from a list of 50 contacts stored in the order they were added, not alphabetically, and you will search only once. Binary search or linear search?

    Hint: What does binary search require of the list?

  6. A student's code uses 'if target > arr[mid]: low = mid'. Searching for 9 in [3, 9], it never stops. Trace why and correct the line.

    Hint: Start with low = 0 and high = 1. What happens to mid?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Is binary search a divide-and-conquer algorithm?

Textbooks disagree. It does divide the range in half, and its cost fits the divide-and-conquer recurrence as T(n)=T(n/2)+O(1)T(n) = T(n/2) + O(1), with just one subproblem. But it never solves the other half or combines answers, so some authors call it decrease and conquer instead. What matters on an exam is the behavior: one comparison, one half kept, O(log⁡n)O(\log n) steps in total.

Why does a billion items need only twice as many checks as 30,000?

Because each extra check doubles how many items you can handle. At most 15 checks cover 32,767 items, since 215−1=32,7672^{15} - 1 = 32{,}767, while 30 checks cover 230−12^{30} - 1, just over a billion. Growing the data more than 30,000 times over only doubles the work. That is what O(log⁡n)O(\log n) growth means in practice.

Can binary search tell me where a missing item would go?

Yes. Run the search as usual; when low passes high and the target was not found, low has stopped at the position where the target belongs to keep the list sorted. Searching for 25 in [10, 20, 30, 40] ends with low = 2, so 25 goes between 20 and 30. Python's bisect module does exactly this, which is how sorted lists stay sorted as new items arrive.

Learning Path

Binary Search

You are here

Next →

Linear Search
You need Searching (finding a target and reporting 'not found'), Array (index access) and Algorithm Efficiency (why O(log⁡n) beats O(n)) first. Binary Search adds the exact loop: low, high, mid, the ±1 updates and the low ≤ high stopping rule. Next, Linear Search covers what binary search cannot handle, unsorted data, and shows when the simpler method is the better choice.

See Also