Suppose you’re searching for a person in the phone book (what an old fashioned sentence!). Their name starts with K. You could start at the beginning and keep flipping pages until you get to the Ks. But you’re more likely to start at a page in the middle, because you know the Ks are going to be near the middle of the phone book.
For example, I’m thinking of a number between 1 and 100. You have to try to guess my number in the fewest tries possible. With every guess, I’ll tell you if your guess is too low, too high, or correct.
If you start guessing like this: 1, 2, 3, 4 …, that would be silly. With each guess, you’re eliminating only one number. If my number was 99, it could take you 99 guesses to get there!
Here’s a better technique. Start with 50. If it's too low, then you just eliminated half the numbers! Now you know that the answer is between 50 and 100.
Next guess is 75. Suppose too high, but again you cut down half the remaining numbers! With binary search, you guess the middle number and eliminate half the remaining numbers every time. Next is 63 (halfway between 50 and 75).
Whatever number I’m thinking of, you can guess in a maximum of seven guesses—because you eliminate so many numbers with every guess!
In general, for any list of n, binary search will take log2 n steps to run in the worst case, whereas simple search will take n steps.
This is binary search. You just learned your first algorithm!
网友评论