Lesson 8: Binary search

Let's play a guessing game: I picked a number between 1 and 100, and each guess I say 'too high' or 'too low'. The smart move: guess the middle each time and rule out half the options. That's exactly 'binary search' — an algorithm that finds a value in a sorted list, halving the candidates every ste

Binary search is like looking up a word in a thick dictionary: you don't read page by page from the start. You open to the middle, and if your word comes later in the alphabet, you toss the whole first half at once. Each peek cuts what's left to search in half.

binary search: A search algorithm on a sorted array that at each step checks the middle and discards the half that cannot contain the target — O(log n).
logarithmic time: O(log n): the number of steps grows very slowly — each doubling of n adds just one step, because the search space is halved each time.
search space: The range of indices [low, high] that may still contain the target; binary search shrinks it by 2x each iteration.