# Exercise: Find the Song

A music app's search box freezes on a million songs: write the catalog's search so it reads at most 20 titles, keep the playlist search that reads from the top, count what each one reads, and let the tests check them, edge cases and 10,000 searches included.

Apprentice · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

Here's the ticket from the music app's search team:

> Our catalog has grown to a million songs, and the search box looks a title up on every keystroke. Today's search reads the titles from the top, so a song that isn't there costs a million reads per keystroke, and the box freezes while people type.
>
> 1. **The catalog arrives sorted A to Z** every night. You can count on that order.
> 2. **A catalog search reads at most 20 titles** in a million songs, found or not, and 10,000 searches finish in under a second.
> 3. **Playlists aren't sorted.** They keep the search that reads from the top, so it has to work on any order.
> 4. **We want to see the difference:** for each search, count how many titles it reads.

You've met both searches in this chapter, and now you write them for real. The tests try the edge cases where searches go wrong, then a library of 1,000 songs, then the ticket's catalog: 10,000 searches in a million songs, in under a second.

## Before you start

You need one language set up, as in *Setup: VS Code and Your Language*. The exercise is written in all five of the course's languages; pick the one you use.

## Get the exercise code

Open this lesson's GitHub repository, [github.com/ask-codey/exercise-ds-find-the-song](https://github.com/ask-codey/exercise-ds-find-the-song), also linked from the **Exercise** box beside the lesson. Clone it into your course folder. In a terminal, in that folder:

```bash
git clone https://github.com/ask-codey/exercise-ds-find-the-song.git
```

Git makes a folder, `exercise-ds-find-the-song`, with the exercise code inside.

The repository has a folder for each language: `csharp`, `java`, `python`, `javascript` and `typescript`. Each folder holds:

- **your code:** one file with four functions to finish, two for playlists and two for the catalog (the repository's `README.md` names the file for each language);
- **the tests** that check your functions. You don't need to change them;
- **a demo program** that tries your functions on the lesson's 16-song library and on a library of 1,000 songs.

In VS Code, choose **File > Open Folder** and open **your language's folder**, not the whole repository.

## What to do

Every function is already there, with its parameters, and returns `-1` or `0` for now. The comment above each one says what it should return, with examples. Here is the first one in Python, as the starter has it (the other languages say the same in their own syntax):

```python
def linear_search(songs, title):
    """
    Look at each song in turn, from the first, and give back the
    position of the first one whose title matches. Give back -1 when
    the title isn't in the list. The list can be in any order.
    Capital letters count: "Slow Rain" and "slow rain" are different.

    linear_search(["Midnight Bus", "Lemon Skies", "Slow Rain"], "Slow Rain") -> 2
    linear_search(["Midnight Bus", "Lemon Skies", "Slow Rain"], "Blue Hour") -> -1

    Growth rate: (write it here)
    """
    return -1
```

1. **The playlist search.** Finish `linearSearch` (`linear_search` in Python, `LinearSearch` in C#): the position of the first song with the title, read from the top, or -1.
2. **Count its reads.** Finish `linearLooks`: how many titles that search reads, up to and including the match, or all of them when the song is missing.
3. **The catalog search.** Finish `binarySearch` for a list sorted A to Z: at most 20 reads in a million songs.
4. **Count its reads.** Finish `binaryLooks`: how many titles your catalog search reads.
5. **Name the growth rates.** On each search's **Growth rate:** line, write its Big-O and a few words on why.

## Check your work

Each language has its own command, run in the terminal in your language's folder (**Terminal > New Terminal** in VS Code). The repository's `README.md` has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (`npm install`).

| Language | Run the tests | Run the demo |
|---|---|---|
| C# | `dotnet test` | `dotnet run --project FindTheSong` |
| Java | `./mvnw test` (`.\mvnw test` in PowerShell) | `java src/main/java/Demo.java` |
| Python | `python -m pytest` | `python demo.py` |
| JavaScript | `npm test` | `node demo.js` |
| TypeScript | `npm test` | `node demo.ts` |

At first all 9 tests fail. That's expected: each function you finish turns its tests green. A failing test's message starts with **Not yet:** and says what it expected, for example *Not yet: Orange Sky would come between Neon Garden and Paper Boats, and it isn't there.*

&lt;details>
&lt;summary>Stuck?&lt;/summary>

- **Where to look:** the catalog search is the one from *One Song in a Million, in 20 Looks: Binary Search*; the playlist search is *Is That Song in My Library? Linear Search*.
- **A linear search is a loop, a match and a `return -1` after the loop.** Return as soon as you find the song. Counting its reads is the same loop with a counter that stops at the match.
- **The catalog search keeps going while `low <= high`.** When the middle title comes before the one you want, move `low` to `middle + 1`; when it comes after, move `high` to `middle - 1`.
- **The tests are the edge cases:** the first and last songs, songs missing before, after and in between, a one-song library and an empty one. If one fails, check it against the off-by-one table in the binary search lesson.
- **Compare titles the lesson's way:** `string.CompareOrdinal` in C#, `compareTo` in Java, `<` in Python, JavaScript and TypeScript.

&lt;/details>

## When you're done

Every test is green, and the demo prints the same four lines in every language:

```text
Library: 16 songs, A to Z
Quiet Harbor: linear finds position 12 in 13 looks; binary finds position 12 in 4 looks
Orange Sky: linear finds position -1 in 16 looks; binary finds position -1 in 4 looks
1,000 songs, the last one: linear takes 1000 looks; binary takes 10 looks
```

Now look at the last line. For a million songs, how many reads would each search take for the last song? And what had to be true of the catalog before the faster search could be used at all?

&lt;details>
&lt;summary>Why Should I Choose This?&lt;/summary>

The ticket's test is 10,000 searches in a million songs. Reading from the top costs about 500,000 titles a search, 5 billion for the test: measured, it got through fewer than 3,000 of the 10,000 searches in the second in every language, and the whole run would take from about 17 seconds in JavaScript to about 2 minutes in Python. Jumping to the first letter still reads tens of thousands of titles a search, and skipping ahead 1,000 at a time about 2,000. Halving reads at most 20, so the test takes a fraction of a second. What it gives up: it needs the catalog sorted. Here the sort is done once a night, before anyone searches; a playlist that's searched once isn't worth sorting, so it keeps the search that reads from the top.

&lt;/details>

## Where else does this shape show up?

You've used "look in the middle, and throw away the half it can't be in". Before you open the answers, think of three other places, at work or in daily life, where you find something by halving what's left.

&lt;details>
&lt;summary>Some answers&lt;/summary>

- **Finding the change that broke an app:** a team with 1,000 changes since the last good version tests the one in the middle, and keeps the half where the bug appeared. About 10 tests find it (Git does this for you with `git bisect`).
- **Finding the line that breaks a program:** comment out half the code; if the error goes, it was in that half.
- **Finding a word in a paper dictionary**, or a name in a phone book.
- **The guessing game**, "higher or lower?", which never needs more than 7 guesses for a number from 1 to 100.
- **Finding the dead bulb in a string of lights:** test the middle of the string, then the half that's dark.

&lt;/details>

## Submit your exercise

The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.

1. On GitHub, click **+**, then **New repository**. Name it (for example `exercise-ds-find-the-song`), choose **Public**, and click **Create repository**. Leave out the README: your folder already has one.
2. In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:

   ```bash
   git remote set-url origin https://github.com/your-name/exercise-ds-find-the-song.git
   git add .
   git commit -m "My solution"
   git push -u origin main
   ```

3. Paste your repo's address, such as `https://github.com/your-name/exercise-ds-find-the-song`, into **Submit your exercise** on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.

Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.

## So what

You've written the two searches every app is built on and watched one take 1,000 reads where the other takes 10, and a million where the other takes 20. The fast one only worked because the catalog was already sorted, so the next chapter asks the obvious question: how do you sort it?

## Key terms

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

## Related

- [Is That Song in My Library? Linear Search](https://www.ask-codey.com/lessons/ds-linear-search)
- [One Song in a Million, in 20 Looks: Binary Search](https://www.ask-codey.com/lessons/ds-binary-search)

Source: https://www.ask-codey.com/lessons/exercise-ds-find-the-song
