Binary search

JavaScript · Unit 22: Searching and sorting

Full plan
JavaScript
10 exercises

If the list already comes sorted, searching one by one wastes that order. Look at the number in the middle: that alone tells you which side your value is on.

And you throw the other side away without looking at it.

const ns = [2, 5, 8, 11, 14, 17];
const mid = Math.floor((0 + 5) / 2);
console.log("looking at", ns[mid]);
console.log(11 > ns[mid]);

Prints

looking at 8
true

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

1. Complete the code
Complete it to look at the middle number of the stretch that runs from lo to hi.
2. Predict the output
Every number the search looks at gets printed. What does it print?
3. Multiple choice
Why does binary search need the list to be sorted?
4. Predict the output
The list isn't sorted, and the 9 gets searched two ways. What does it print?
5. Find the bug
The list is sorted and the 14 sits at position 4, so this should print 4. Which line has the error?
6. Put the lines in order
Put in order the function that decides what comes next after looking at the middle number: if it's the one you want, done; if it's smaller, you keep going to the right; otherwise, to the left.
7. Find the case that fails
where(ns, v) takes a sorted list and returns the position of v, or -1 if it isn't there; with an empty list it also returns -1. Which call does it fail on?
8. Predict the output
rounds counts how many times a number gets looked at while searching for the 8. What does it print?
9. Complete the code
Complete it to get the sorted copy binary search needs, without shuffling the original list.
10. Multiple choice
You have an unsorted list of 100 names and you need to find one, just once. What's the better move?

Do this lesson

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.

See all lessons →