Binary search: halve the search — Computing, 7–10
When a list is already in order, you do not need to check every item one by one. Binary search looks at the middle, decides which half could contain the answer, and repeats until the item is found or ruled out.
Always cut the possibilities in half
Suppose a secret number is hidden in an ordered row. Instead of starting at the first number, ask about the middle one. If your target is larger, ignore the lower half; if it is smaller, ignore the upper half. Each answer removes about half the choices, so the search quickly becomes small.
Why not check every item?
Looking from the start works for a short list, but it becomes slow when there are thousands or millions of ordered items. Binary search uses the order as a clue, rather than throwing that clue away. It was developed from the sensible question: how can we rule out as many wrong places as possible with one check?
Finding 73 in a list
The ordered list is 12, 25, 31, 44, 58, 73, 81, 90. First, check the middle: 44. Since 73 is larger, keep 58, 73, 81, 90. Check the middle of these: 73. The target is found after two checks, rather than checking all eight numbers from the beginning.
The order is essential
It is reasonable to use the middle of any list, because the middle feels like a useful shortcut. But if the list is 12, 90, 25, 73, 44, 81, 31, 58, seeing 44 tells you nothing about which half holds 73. Binary search only works when the list is ordered by the same thing you are comparing.
Finding things quickly
A dictionary uses alphabetic order, so you can open near the middle and narrow the search for a word. Computer programs use the same strategy in ordered names, numbers and records. It is useful when a list is large and already sorted; sorting it first may cost extra work, so the shortcut is not always the best choice.
Keep exploring
Other languages
Loading MyLeoNes™…