Binary Search
If a list is sorted, you can do far better. Look at the middle item. If it is the target, done. If the target is smaller, the answer can only be in the left half; if larger, the right half. Throw the other half away and repeat.
Each step halves the search area, so 1,000,000 items need only about 20 steps: O(log n). The price is that the list must already be sorted.
Keep two markers, low and high, around the part still possible, and move one of them each round.
What must be true of a list before binary search works?
Count the steps binary search needs to find 70 in the list and print the step count.
Finish the quick check (and any code exercise) to complete this lesson, or mark it done yourself.
Tip: use the left and right arrow keys to move between lessons.