# One Song in a Million, in 20 Looks: Binary Search

Find one song among a million in about 20 looks, on every keystroke: why checking every song, jumping to the first letter and skipping ahead by 1,000 all fall short, and the search that fixes them, binary search, written so it's right at the edges.

Apprentice · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Write a binary search over a sorted list with low, middle and high, and test its edge cases
- Explain why binary search needs sorted data and takes O(log n) steps
- Choose between checking every item and sorting once to search by halving, for a search job, and say why

## Key takeaways

- Binary search looks at the middle of what's left, then keeps only the half the item could be in. It needs the list sorted.
- Three numbers do the work: low and high mark what's left, and middle is the one you look at.
- It is O(log n): doubling the list adds only one more look, so a million songs take about 20.
- Test it with the first item, the last item and missing items, because the off-by-one mistakes hide at the edges.
- Sorting a million songs costs about 20 million steps, so sorting once and searching by halving pays off when the same list is searched many times.

**Before this:** *Is That Song in My Library? Linear Search* (a missing song in a million takes a million looks, on every keystroke).

Your music app's library has grown to a million songs, and this time it's kept in A to Z order by title, the way the app lists them. The search box looks a title up on every keystroke, so a search has to answer before the next key is pressed. Linear search reads up to a million titles per keystroke, and the box freezes as people type.

## What would you try?

**Check every song, from the top.** That's linear search: up to 1,000,000 looks for a missing song, about 500,000 on average.

**Jump to the first letter.** The list is A to Z, so start at the first song beginning with Q. If titles spread evenly over 26 letters, that's still about 38,000 Q songs to check one by one, and a busy letter like S holds far more. Better, but still O(n): twice the songs, twice the songs per letter.

**Skip ahead 1,000 songs at a time.** Look at song 1,000, then 2,000, then 3,000, until you pass *Quiet Harbor*, then step back through the last 1,000 one by one. That's up to 1,000 jumps plus up to 1,000 steps: about 2,000 looks. Much better: each jump looked at one title and skipped 999 others.

| What we tried | Looks for one search | Where it breaks |
|---|---|---|
| Every song from the top | up to 1,000,000 | every keystroke reads the whole library |
| Jump to the first letter | about 38,000, more for busy letters | each letter still holds tens of thousands of songs |
| Skip ahead 1,000 at a time | about 2,000 | it still steps through a thousand songs at the end |

## The questions that lead to it

**Why could the skips work at all?** Because the list is in order. When song 412,000 is *Paper Boats*, every song before it comes before *Paper Boats* in the alphabet, so *Quiet Harbor* can't be there. One look ruled out 412,000 songs.

**How do you find "quiet" in a paper dictionary?** You don't start at A, or at the first page of Q. You open it near the middle and see "magnet". "Quiet" comes after "magnet", so the whole front half of the book goes, in one look. Then you open the back half near its middle, and do it again.

**What's the most one look can rule out?** Look at the middle, and whichever way the answer goes, half of what's left is gone. Half of a million, then half of that, again and again: how many looks until one song is left?

## How it got its name

This idea was so useful that it got a name: **binary search**. "Binary" means made of two: every look splits what's left into two halves and keeps one. You've met its counting in *How Many Times Can You Halve a Million? O(log n)*: a million halves down to one song in about 20 steps. Now it's a search.

It needs one thing: the list must be **sorted** by what you search for. On a jumbled list, the middle song tells you nothing about where the others are.

## The rule: low, middle and high

Binary search keeps three numbers, all positions in the list:

- **low**: the first position the song could still be at;
- **high**: the last position it could still be at;
- **middle**: the one you look at, halfway between them: (low + high) ÷ 2, rounded down.

Then it repeats one step. Look at the middle song. If it's the one you want, you're done. If it comes **before** the one you want, the song can only be after it, so low moves to middle + 1. If it comes **after**, high moves to middle − 1. When low passes high, nothing is left: the song isn't there.

## Binary search in code

Here is a library of 16 songs, sorted A to Z, and a search for *Quiet Harbor* that prints every look:

```csharp
List<string> library = new List<string> { "Amber Road", "Blue Hour", "Copper Moon", "Desert Lights", "Echo Park", "Falling Up", "Golden Hour", "Harbor Lights", "Lemon Skies", "Midnight Bus", "Neon Garden", "Paper Boats", "Quiet Harbor", "Slow Rain", "Sunday Static", "Velvet Train" };
string title = "Quiet Harbor";

int low = 0;
int high = library.Count - 1;
int found = -1;
int looks = 0;
while (low <= high)
{
    int middle = (low + high) / 2;
    looks++;
    Console.WriteLine("Look " + looks + ": low " + low + ", middle " + middle + ", high " + high + ": " + library[middle]);
    int comparison = string.CompareOrdinal(library[middle], title);
    if (comparison == 0)
    {
        found = middle;
        break;
    }
    if (comparison < 0)
    {
        low = middle + 1;
    }
    else
    {
        high = middle - 1;
    }
}
Console.WriteLine(title + ": position " + found);
```

```text
Look 1: low 0, middle 7, high 15: Harbor Lights
Look 2: low 8, middle 11, high 15: Paper Boats
Look 3: low 12, middle 13, high 15: Slow Rain
Look 4: low 12, middle 12, high 12: Quiet Harbor
Quiet Harbor: position 12
```

```java
void main() {
    List<String> library = List.of("Amber Road", "Blue Hour", "Copper Moon", "Desert Lights", "Echo Park", "Falling Up", "Golden Hour", "Harbor Lights", "Lemon Skies", "Midnight Bus", "Neon Garden", "Paper Boats", "Quiet Harbor", "Slow Rain", "Sunday Static", "Velvet Train");
    String title = "Quiet Harbor";

    int low = 0;
    int high = library.size() - 1;
    int found = -1;
    int looks = 0;
    while (low <= high) {
        int middle = (low + high) / 2;
        looks++;
        IO.println("Look " + looks + ": low " + low + ", middle " + middle + ", high " + high + ": " + library.get(middle));
        int comparison = library.get(middle).compareTo(title);
        if (comparison == 0) {
            found = middle;
            break;
        }
        if (comparison < 0) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    IO.println(title + ": position " + found);
}
```

```text
Look 1: low 0, middle 7, high 15: Harbor Lights
Look 2: low 8, middle 11, high 15: Paper Boats
Look 3: low 12, middle 13, high 15: Slow Rain
Look 4: low 12, middle 12, high 12: Quiet Harbor
Quiet Harbor: position 12
```

```python
library = ["Amber Road", "Blue Hour", "Copper Moon", "Desert Lights", "Echo Park", "Falling Up", "Golden Hour", "Harbor Lights", "Lemon Skies", "Midnight Bus", "Neon Garden", "Paper Boats", "Quiet Harbor", "Slow Rain", "Sunday Static", "Velvet Train"]
title = "Quiet Harbor"

low = 0
high = len(library) - 1
found = -1
looks = 0
while low <= high:
    middle = (low + high) // 2
    looks += 1
    print(f"Look {looks}: low {low}, middle {middle}, high {high}: {library[middle]}")
    if library[middle] == title:
        found = middle
        break
    if library[middle] < title:
        low = middle + 1
    else:
        high = middle - 1
print(f"{title}: position {found}")
```

```text
Look 1: low 0, middle 7, high 15: Harbor Lights
Look 2: low 8, middle 11, high 15: Paper Boats
Look 3: low 12, middle 13, high 15: Slow Rain
Look 4: low 12, middle 12, high 12: Quiet Harbor
Quiet Harbor: position 12
```

```javascript
const library = ["Amber Road", "Blue Hour", "Copper Moon", "Desert Lights", "Echo Park", "Falling Up", "Golden Hour", "Harbor Lights", "Lemon Skies", "Midnight Bus", "Neon Garden", "Paper Boats", "Quiet Harbor", "Slow Rain", "Sunday Static", "Velvet Train"];
const title = "Quiet Harbor";

let low = 0;
let high = library.length - 1;
let found = -1;
let looks = 0;
while (low <= high) {
  const middle = Math.floor((low + high) / 2);
  looks++;
  console.log(`Look ${looks}: low ${low}, middle ${middle}, high ${high}: ${library[middle]}`);
  if (library[middle] === title) {
    found = middle;
    break;
  }
  if (library[middle] < title) {
    low = middle + 1;
  } else {
    high = middle - 1;
  }
}
console.log(`${title}: position ${found}`);
```

```text
Look 1: low 0, middle 7, high 15: Harbor Lights
Look 2: low 8, middle 11, high 15: Paper Boats
Look 3: low 12, middle 13, high 15: Slow Rain
Look 4: low 12, middle 12, high 12: Quiet Harbor
Quiet Harbor: position 12
```

```typescript
const library: string[] = ["Amber Road", "Blue Hour", "Copper Moon", "Desert Lights", "Echo Park", "Falling Up", "Golden Hour", "Harbor Lights", "Lemon Skies", "Midnight Bus", "Neon Garden", "Paper Boats", "Quiet Harbor", "Slow Rain", "Sunday Static", "Velvet Train"];
const title = "Quiet Harbor";

let low = 0;
let high = library.length - 1;
let found = -1;
let looks = 0;
while (low <= high) {
  const middle = Math.floor((low + high) / 2);
  looks++;
  console.log(`Look ${looks}: low ${low}, middle ${middle}, high ${high}: ${library[middle]}`);
  if (library[middle] === title) {
    found = middle;
    break;
  }
  if (library[middle] < title) {
    low = middle + 1;
  } else {
    high = middle - 1;
  }
}
console.log(`${title}: position ${found}`);
```

```text
Look 1: low 0, middle 7, high 15: Harbor Lights
Look 2: low 8, middle 11, high 15: Paper Boats
Look 3: low 12, middle 13, high 15: Slow Rain
Look 4: low 12, middle 12, high 12: Quiet Harbor
Quiet Harbor: position 12
```

A note on the languages: "comes before" for text means A to Z order, letter by letter. Python, JavaScript and TypeScript compare two strings with `<`. C# and Java can't, so they ask `string.CompareOrdinal(a, b)` or `a.compareTo(b)`, which answer with a number: below zero when `a` comes first, zero when they're equal, above zero when `a` comes after.

![The 16 sorted song titles in a row of boxes numbered 0 to 15, drawn four times, once per look: each row marks low, middle and high, shades the positions still possible, and the shaded part halves from 16 songs to 8, 4 and 1 until the fourth look lands on Quiet Harbor at position 12](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/e22661cce8b94c269a95bd7fcf883877.webp)

Four looks for 16 songs. A linear search would have read 13 titles to reach position 12.

## The off-by-one traps

Binary search is short, and nearly every line can be off by one: one position too far, or one too few. Each of these small changes still finds most songs, which is why the mistake survives until someone searches for the wrong one:

| The mistake | What goes wrong |
|---|---|
| `while low < high` instead of `low <= high` | when one song is left (low equals high), the loop stops without looking at it: *Amber Road*, *Velvet Train* and even *Quiet Harbor* come back as missing |
| `high = length` instead of `length - 1` | a search for a title after the last song reads one past the end of the list and crashes |
| `high = middle` instead of `middle - 1` | the middle song is never ruled out, so a search for a missing title can loop forever |

An off-by-one mistake has its own name: an **off-by-one error**. The way to catch one is to test the **edge cases**, the places where something starts, stops or isn't there, not only a song in the middle:

```csharp
List<string> library = new List<string> { "Amber Road", "Blue Hour", "Copper Moon", "Desert Lights", "Echo Park", "Falling Up", "Golden Hour", "Harbor Lights", "Lemon Skies", "Midnight Bus", "Neon Garden", "Paper Boats", "Quiet Harbor", "Slow Rain", "Sunday Static", "Velvet Train" };

int BinarySearch(List<string> songs, string title)
{
    int low = 0;
    int high = songs.Count - 1;
    while (low <= high)
    {
        int middle = (low + high) / 2;
        int comparison = string.CompareOrdinal(songs[middle], title);
        if (comparison == 0)
        {
            return middle;
        }
        if (comparison < 0)
        {
            low = middle + 1;
        }
        else
        {
            high = middle - 1;
        }
    }
    return -1;
}

Console.WriteLine("First, Amber Road: " + BinarySearch(library, "Amber Road"));
Console.WriteLine("Last, Velvet Train: " + BinarySearch(library, "Velvet Train"));
Console.WriteLine("Missing, before the first: " + BinarySearch(library, "Above the Clouds"));
Console.WriteLine("Missing, after the last: " + BinarySearch(library, "Window Seat"));
Console.WriteLine("Missing, in between: " + BinarySearch(library, "Orange Sky"));
```

```text
First, Amber Road: 0
Last, Velvet Train: 15
Missing, before the first: -1
Missing, after the last: -1
Missing, in between: -1
```

```java
List<String> library = List.of("Amber Road", "Blue Hour", "Copper Moon", "Desert Lights", "Echo Park", "Falling Up", "Golden Hour", "Harbor Lights", "Lemon Skies", "Midnight Bus", "Neon Garden", "Paper Boats", "Quiet Harbor", "Slow Rain", "Sunday Static", "Velvet Train");

int binarySearch(List<String> songs, String title) {
    int low = 0;
    int high = songs.size() - 1;
    while (low <= high) {
        int middle = (low + high) / 2;
        int comparison = songs.get(middle).compareTo(title);
        if (comparison == 0) {
            return middle;
        }
        if (comparison < 0) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    return -1;
}

void main() {
    IO.println("First, Amber Road: " + binarySearch(library, "Amber Road"));
    IO.println("Last, Velvet Train: " + binarySearch(library, "Velvet Train"));
    IO.println("Missing, before the first: " + binarySearch(library, "Above the Clouds"));
    IO.println("Missing, after the last: " + binarySearch(library, "Window Seat"));
    IO.println("Missing, in between: " + binarySearch(library, "Orange Sky"));
}
```

```text
First, Amber Road: 0
Last, Velvet Train: 15
Missing, before the first: -1
Missing, after the last: -1
Missing, in between: -1
```

```python
library = ["Amber Road", "Blue Hour", "Copper Moon", "Desert Lights", "Echo Park", "Falling Up", "Golden Hour", "Harbor Lights", "Lemon Skies", "Midnight Bus", "Neon Garden", "Paper Boats", "Quiet Harbor", "Slow Rain", "Sunday Static", "Velvet Train"]


def binary_search(songs, title):
    low = 0
    high = len(songs) - 1
    while low <= high:
        middle = (low + high) // 2
        if songs[middle] == title:
            return middle
        if songs[middle] < title:
            low = middle + 1
        else:
            high = middle - 1
    return -1


print(f"First, Amber Road: {binary_search(library, 'Amber Road')}")
print(f"Last, Velvet Train: {binary_search(library, 'Velvet Train')}")
print(f"Missing, before the first: {binary_search(library, 'Above the Clouds')}")
print(f"Missing, after the last: {binary_search(library, 'Window Seat')}")
print(f"Missing, in between: {binary_search(library, 'Orange Sky')}")
```

```text
First, Amber Road: 0
Last, Velvet Train: 15
Missing, before the first: -1
Missing, after the last: -1
Missing, in between: -1
```

```javascript
const library = ["Amber Road", "Blue Hour", "Copper Moon", "Desert Lights", "Echo Park", "Falling Up", "Golden Hour", "Harbor Lights", "Lemon Skies", "Midnight Bus", "Neon Garden", "Paper Boats", "Quiet Harbor", "Slow Rain", "Sunday Static", "Velvet Train"];

function binarySearch(songs, title) {
  let low = 0;
  let high = songs.length - 1;
  while (low <= high) {
    const middle = Math.floor((low + high) / 2);
    if (songs[middle] === title) {
      return middle;
    }
    if (songs[middle] < title) {
      low = middle + 1;
    } else {
      high = middle - 1;
    }
  }
  return -1;
}

console.log(`First, Amber Road: ${binarySearch(library, "Amber Road")}`);
console.log(`Last, Velvet Train: ${binarySearch(library, "Velvet Train")}`);
console.log(`Missing, before the first: ${binarySearch(library, "Above the Clouds")}`);
console.log(`Missing, after the last: ${binarySearch(library, "Window Seat")}`);
console.log(`Missing, in between: ${binarySearch(library, "Orange Sky")}`);
```

```text
First, Amber Road: 0
Last, Velvet Train: 15
Missing, before the first: -1
Missing, after the last: -1
Missing, in between: -1
```

```typescript
const library: string[] = ["Amber Road", "Blue Hour", "Copper Moon", "Desert Lights", "Echo Park", "Falling Up", "Golden Hour", "Harbor Lights", "Lemon Skies", "Midnight Bus", "Neon Garden", "Paper Boats", "Quiet Harbor", "Slow Rain", "Sunday Static", "Velvet Train"];

function binarySearch(songs: string[], title: string): number {
  let low = 0;
  let high = songs.length - 1;
  while (low <= high) {
    const middle = Math.floor((low + high) / 2);
    if (songs[middle] === title) {
      return middle;
    }
    if (songs[middle] < title) {
      low = middle + 1;
    } else {
      high = middle - 1;
    }
  }
  return -1;
}

console.log(`First, Amber Road: ${binarySearch(library, "Amber Road")}`);
console.log(`Last, Velvet Train: ${binarySearch(library, "Velvet Train")}`);
console.log(`Missing, before the first: ${binarySearch(library, "Above the Clouds")}`);
console.log(`Missing, after the last: ${binarySearch(library, "Window Seat")}`);
console.log(`Missing, in between: ${binarySearch(library, "Orange Sky")}`);
```

```text
First, Amber Road: 0
Last, Velvet Train: 15
Missing, before the first: -1
Missing, after the last: -1
Missing, in between: -1
```

These five searches catch all three mistakes in the table. **Try it.** Make one of the mistakes on purpose, run the code again, and see which line changes (for `high = middle`, stop the program with **Ctrl+C** if it never finishes).

## Why it's O(log n)

Every look halves what's left: 16 songs, then 8, 4, 2, 1. That's the halving count from *How Many Times Can You Halve a Million? O(log n)*, so binary search is **O(log n)**, read "big O of log n": double the songs, one more look. About 10 looks for 1,000 songs, 20 for a million, 30 for a billion. The search box that froze at a million looks a keystroke now does 20.

## The price of admission: a sorted list

The list must be sorted, and kept sorted when songs are added. Sorting isn't free: a million songs take about 20 million steps with a good sort (the rest of this module is about sorting). So compare:

- **A linear search** for a missing song: 1,000,000 looks, every time.
- **Sort once, then binary search:** about 20,000,000 steps once, then 20 looks a search.

The sort pays for itself after about 20 searches for songs that aren't there, or about 40 for songs found halfway down. A search box gets there before you've typed two titles. A list searched once or twice isn't worth sorting: linear search wins.

## When something else wins

- **A list that changes all day.** Every new song has to slide the songs after it along to reach its place: O(n) per song.
- **Exact titles only.** If the app only ever asks "is this exact title here?", Module 5's hash table answers in about one step without sorting at all. But it can't answer "every title starting with Qu" or "everything from A to C". A sorted list can, with the same halving: search for "Qu", and the place where it would go is where the Qu titles start. That's what a search box that suggests as you type needs.

## Your language's version

Your language has binary search built in for sorted lists: `List<T>.BinarySearch` in C#, `Collections.binarySearch` in Java and Python's `bisect` module. JavaScript and TypeScript have none built in, so there the function above is the answer. In C# and Java, a missing item gives back a negative number rather than exactly -1.

**In your textbook** you may see the middle written `low + (high - low) / 2`. It gives the same middle, and in C# and Java it can't overflow: with more than about a billion items, `low + high` is too big for an `int`.

## The cost card

| Operation | Big-O | The everyday reason |
|---|---|---|
| Find an item, best case | O(1) | the very first guess, the middle, is the answer |
| Find an item, worst case | O(log n) | every look throws away half of what's left |
| Sort it first, once | O(n log n) | about 20 million steps for a million songs, paid back after about 20 searches |
| Keep it searchable | sorted data | "comes after" only tells you something when the list is in order |
| Extra memory | O(1) | three numbers: low, middle and high |

## Check yourself

2 questions to try on the lesson page.

## So what

Binary search turns a million looks into 20, which is why sorted data is worth so much and why "is it sorted?" is the first question to ask about any slow search. Write it with `low <= high` and `middle ± 1`, and test the first item, the last item and a few missing ones before you trust it. Then ask the next question: how do you get a big list sorted in the first place?

## Key terms

- [Binary Search](https://www.ask-codey.com/glossary/binary-search)
- [Logarithmic Time](https://www.ask-codey.com/glossary/logarithmic-time)
- [Off-By-One Error](https://www.ask-codey.com/glossary/off-by-one-error)
- [Edge Case](https://www.ask-codey.com/glossary/edge-case)

## Cheat sheets

- [One Song in a Million, in 20 Looks: Binary Search](https://www.ask-codey.com/cheat-sheets/ds-binary-search-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-binary-search
