In order first

The fare board is sorted now, cheapest first. Where does 24 sit? Low and high are the ends of the part still searched. Mid is the position between them.

The rule

24 is at position 4. The steps find it in three checks. The target is the fare we look for. The code calls it wanted.

Sort the list first. Then check the middle. If it matches, stop. If it is smaller than the target, search the right half. If it is bigger, search the left half. No part left means not found.

This is binary search. Each check rules out about half of what is left.

On seven fares it needs at most 3 checks. Seven, then three, then one.

In the code, lo and hi mean low and high. The name mid is the middle position.

`` function findFare(fares, wanted, lo, hi) { while (lo <= hi) { const mid = floor((lo + hi) / 2); if (fares[mid] === wanted) { return mid; } if (fares[mid] < wanted) { lo = mid+1; } else { hi = mid-1; } } return -1; } ``

Here board is the sorted board. Start with lo at 0 and hi at 6, the last position. floor rounds down. findFare(board, 24, 0, 6) gives 4. That is the position, not just yes or no. A missing fare gives −1. Positions start at 0, so −1 is not a position.

A look at the middle has three results: equal, smaller, bigger. Checking the middle three ways counts as one comparison.

Tap the half to search next. Try all three fares.

Try the lab to finish this lesson.