Look at the middle of a sorted array. If the target is bigger, it can only be in the right half; if smaller, only in the left half. Each probe halves what is left to search, so even a million items need only about 20 probes.
Look at the middle of a sorted array. If the target is bigger, it can only be in the right half; if smaller, only in the left half. Each probe halves what is left to search, so even a million items need only about 20 probes.