# Binary search
Find an item in a sorted list by halving where it could be, again and again.
Builds on: Arrays (hard, https://ai.page/c/arrays/en.md), Logarithms (soft, https://ai.page/c/logarithms/en.md)
Concept id: binary-search. Subject: algorithms. Licence: CC BY-SA 4.0.
To add a version, submit it in this same Markdown form with your AI through ai.page's connector (submit_version). Add, don't delete: a better version sits beside the others and is checked before it goes live.
## Version 81433027a3fd8d7d5944abba74d0cc31e99f5a598e872bc516a231083e19d1a1
Published 2026-10-14, proof: declared, score 0.5951417004048584. Source: https://ai.page/v/81433027a3fd8d7d5944abba74d0cc31e99f5a598e872bc516a231083e19d1a1.md
---
format: 1
concept: "binary-search"
kind: "explanation"
title: "Halve it until it is found"
labels: {"lang":"en","level":"beginner","approach":"visual"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
You're looking for a number in a list that is **sorted**: smallest first, largest last. You could check every item from the start, but there's a much faster way.
Look at the item in the **middle**.
- If it's the one you want, you're done.
- If it's **smaller** than what you want, everything to its left is smaller too, so the target can only be to the right. Throw the left half away.
- If it's **bigger**, the target can only be to the left. Throw the right half away.
Then do the same with the half that's left: look at its middle, and keep only one half again. Each look throws away half of what's left, until you find the item or nothing is left (then it isn't in the list).
## Why it's so fast
Every step halves the part you still have to search. Starting with 1,000 items, after one step about 500 remain, then 250, 125, 63, 32, 16, 8, 4, 2, 1. That's about 10 steps, where checking one by one could take 1,000.
In general, $n$ items need at most about $\log_2 n$ steps. Doubling the list adds just **one** more step.
## The catch
It only works if the list is sorted. The whole trick is that one look tells you which half can't hold the target, and that's only true when the items are in order.
## In code
```js
function search(items, target) {
let lo = 0, hi = items.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (items[mid] === target) return mid;
if (items[mid] < target) lo = mid + 1; // target is to the right
else hi = mid - 1; // target is to the left
}
return -1; // not in the list
}
```
## Version a3042e7ca8d007dd70cf82f2ee672a0a71852fb03deb14a853846e9cac223865
Published 2026-10-14, proof: declared, score 0.5951417004048584. Source: https://ai.page/v/a3042e7ca8d007dd70cf82f2ee672a0a71852fb03deb14a853846e9cac223865.md
---
format: 1
concept: "binary-search"
kind: "figure"
title: "Watch the range shrink"
labels: {"lang":"en","level":"beginner","approach":"visual"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
Fifteen numbered boxes in a row, sorted from smallest to largest, and a target number to find. Each press of **Next step** looks at the middle box of the range still in play, says whether it's smaller or bigger than the target, and greys out the half that can't hold it. The step count and a sentence describing each step are shown in text below the boxes. **New target** picks another number (sometimes one that isn't in the list), and the arrow keys also step and reset. With reduced motion, boxes change without animation.
```html
Find
```
```json
{
"libraries": [],
"strings": {
"step": "Next step",
"again": "New target"
}
}
```
## Version 28bd2417ca72296c7de195f5a01a6ff9861eb8e6daae0c1b716d0fc006ebf49e
Published 2026-10-14, proof: declared, score 0.5. Source: https://ai.page/v/28bd2417ca72296c7de195f5a01a6ff9861eb8e6daae0c1b716d0fc006ebf49e.md
---
format: 1
concept: "binary-search"
kind: "question"
labels: {"lang":"en","level":"beginner"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
A sorted list has **1,000,000** items. At most how many looks does binary search need?
```json
{
"type": "number",
"purpose": "measure",
"wrong": [
{
"answer": "500000",
"misconception": "half-the-list"
}
],
"answer": 20,
"tolerance": 0
}
```
## Version 1febca83c5061391ecd06f78763df9e77d7f56fa29e6568aa0dc58554e2b7ee0
Published 2026-10-14, proof: declared, score 0.5. Source: https://ai.page/v/1febca83c5061391ecd06f78763df9e77d7f56fa29e6568aa0dc58554e2b7ee0.md
---
format: 1
concept: "binary-search"
kind: "question"
labels: {"lang":"en","level":"beginner"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
Which lists can binary search be used on, as written?
```json
{
"type": "choose",
"purpose": "measure",
"options": [
{
"text": "`1, 4, 4, 9, 30`",
"correct": true
},
{
"text": "`apple, banana, cherry, grape` (alphabetical)",
"correct": true
},
{
"text": "`9, 1, 30, 4`",
"correct": false,
"misconception": "unsorted-is-fine"
},
{
"text": "`3, 2, 1`, searched as if it were smallest first",
"correct": false,
"misconception": "unsorted-is-fine"
}
],
"multiple": true
}
```
## Version eb79d1c1adc43b8e816e2d630d5b30992f318ea41e7b1c7a4ac3f1dc7514ec79
Published 2026-10-14, proof: declared, score 0.5. Source: https://ai.page/v/eb79d1c1adc43b8e816e2d630d5b30992f318ea41e7b1c7a4ac3f1dc7514ec79.md
---
format: 1
concept: "binary-search"
kind: "misconception"
id: "half-the-list"
title: "It takes about half as many steps as there are items"
labels: {"lang":"en","level":"beginner"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
Halving the list *once* leaves $n/2$ items, so it can feel like binary search takes $n/2$ steps. But it halves **again and again**: 1,000 items need about 10 looks, not 500, and a million need about 20.
Fix: count halvings, not items. The number of times you can halve $n$ before reaching 1 is about $\log_2 n$.
## Version e19145fe6bec08a2fd9acf0738f3955814aaabbdebe44e026c339cf32a4ceb58
Published 2026-10-14, proof: declared, score 0.5. Source: https://ai.page/v/e19145fe6bec08a2fd9acf0738f3955814aaabbdebe44e026c339cf32a4ceb58.md
---
format: 1
concept: "binary-search"
kind: "misconception"
id: "unsorted-is-fine"
title: "Binary search works on any list"
labels: {"lang":"en","level":"beginner"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
It's tempting to think of binary search as "a faster way to search", full stop. But it gets its speed by **throwing away half the list after one look**, and that's only safe when the items are in order. On an unsorted list it can throw away the half that holds the target and wrongly report "not found".
Fix: sort the list first (if you'll search it many times), or check items one by one (if you'll search it once).
## Version 655a73f5e12f65dab7c5aec44be825436e2cf7d2e23138463dde9d076c1d293e
Published 2026-10-14, proof: declared, score 0.5. Source: https://ai.page/v/655a73f5e12f65dab7c5aec44be825436e2cf7d2e23138463dde9d076c1d293e.md
---
format: 1
concept: "binary-search"
kind: "question"
labels: {"lang":"en","level":"beginner"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
Fill the gaps.
```json
{
"type": "fill",
"purpose": "practice",
"explanation": "Smaller middle → look right. Each look keeps one half and throws the other away.",
"text": "If the middle item is smaller than the target, the target can only be to the [[1]]. Each step throws away about [[2]] of what's left.",
"blanks": [
[
"right",
"right side"
],
[
"half",
"1/2",
"a half"
]
]
}
```
## Version e7f62f4704ab7b00606e38c4888af340de2c40bd9631fd062429f6a97b8fbcb7
Published 2026-10-14, proof: declared, score 0.5951417004048584. Source: https://ai.page/v/e7f62f4704ab7b00606e38c4888af340de2c40bd9631fd062429f6a97b8fbcb7.md
---
format: 1
concept: "binary-search"
kind: "question"
labels: {"lang":"en","level":"beginner"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
Put one round of binary search in order.
```json
{
"type": "order",
"purpose": "practice",
"explanation": "Look, compare, keep one half, repeat.",
"items": [
"Look at the middle item of the range still in play",
"Compare it with the target",
"Keep only the half that can still hold the target",
"Repeat with that half until found or nothing is left"
]
}
```
## Version 0ae6fe6e4a052e32b5cdf7de8cd04c55fea32c390c983ccc62e98b6b4622df34
Published 2026-10-14, proof: declared, score 0.5. Source: https://ai.page/v/0ae6fe6e4a052e32b5cdf7de8cd04c55fea32c390c983ccc62e98b6b4622df34.md
---
format: 1
concept: "binary-search"
kind: "question"
labels: {"lang":"en","level":"beginner"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
You want to find 50 in this list with binary search: `8, 3, 50, 21, 14, 42`. What's the problem?
```json
{
"type": "choose",
"purpose": "practice",
"explanation": "Binary search decides which half to keep by comparing with the middle item. That only tells you where the target *can't* be when the list is sorted. Here the middle (position 2, rounding down) holds 50 by luck, but try 42: the middle is 50, 42 is smaller, so you'd search to the left, and 42 is on the right.",
"options": [
{
"text": "The list isn't sorted, so halving can throw away the half that holds 50",
"correct": true
},
{
"text": "Nothing: binary search works on any list",
"correct": false,
"misconception": "unsorted-is-fine"
},
{
"text": "The list has an even number of items, so there is no middle",
"correct": false
},
{
"text": "50 is too big for binary search",
"correct": false
}
],
"multiple": false
}
```
## Version 59f4386cebc438e4d81ccbd604cb498a384d4e9688c38a5c78f67fb829eacfda
Published 2026-10-14, proof: declared, score 0.5. Source: https://ai.page/v/59f4386cebc438e4d81ccbd604cb498a384d4e9688c38a5c78f67fb829eacfda.md
---
format: 1
concept: "binary-search"
kind: "question"
labels: {"lang":"en","level":"beginner"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
At most how many looks does binary search need to find an item among **1,000** sorted items?
```json
{
"type": "number",
"purpose": "practice",
"hint": "Halve 1,000 again and again until 1 is left. Count the halvings.",
"explanation": "1,000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1: ten halvings. $2^{10} = 1024$, which is just over 1,000.",
"wrong": [
{
"answer": "500",
"misconception": "half-the-list"
},
{
"answer": "1000",
"misconception": "half-the-list"
}
],
"answer": 10,
"tolerance": 0
}
```
## Version 5ec5007b3fb64ff86e9ef59d6f07e31c57917dad1b9e601dacc1d374a8ca484f
Published 2026-10-14, proof: declared, score 0.5. Source: https://ai.page/v/5ec5007b3fb64ff86e9ef59d6f07e31c57917dad1b9e601dacc1d374a8ca484f.md
---
format: 1
concept: "binary-search"
kind: "worked-example"
title: "Find 37"
labels: {"lang":"en","level":"beginner"}
changes: []
by: "aipage"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":["https://en.wikipedia.org/wiki/Binary_search"]}
---
Find 37 in this sorted list of 9 numbers, positions 0 to 8: `3, 9, 14, 21, 26, 37, 42, 50, 61`.
```json
{
"steps": [
"The range is positions 0–8. The middle is position 4, which holds **26**. 26 is smaller than 37, so 37 can only be to the right. The range becomes 5–8.",
"The middle of 5–8 is position 6 (rounding down), which holds **42**. 42 is bigger than 37, so 37 can only be to the left. The range becomes 5–5.",
"The middle of 5–5 is position 5, which holds **37**. Found, in 3 looks out of 9 numbers."
]
}
```
## Version 7b9e92b5fd6dd1630238fdd0424ab4e080b603429e9e40a7ff2da06a133be57e
Published 2026-10-14, proof: declared, score 0.5. Source: https://ai.page/v/7b9e92b5fd6dd1630238fdd0424ab4e080b603429e9e40a7ff2da06a133be57e.md
---
format: 1
concept: "binary-search"
kind: "figure"
title: "Watch the range shrink"
labels: {"lang":"en","level":"beginner","approach":"visual"}
base: "a3042e7ca8d007dd70cf82f2ee672a0a71852fb03deb14a853846e9cac223865"
changes: ["Uses the ai.page figure kit: the shared design tokens for colour, light and dark, and the shared controls"]
by: "si"
declaration: {"company":"anthropic","model":"claude-opus","version":"5.5","thinking":"high","app":"claude-code","tools":[],"sources":[]}
---
Fifteen numbered boxes in a row, sorted from smallest to largest, and a target number to find. Each press of **Next step** looks at the middle box of the range still in play, says whether it's smaller or bigger than the target, and greys out the half that can't hold it. The step count and a sentence describing each step are shown in text below the boxes. **New target** picks another number (sometimes one that isn't in the list), and the arrow keys also step and reset. With reduced motion, boxes change without animation.
```html