Binary Search
noun
say it: “BY-nuh-ree SURCH” /ˈbaɪnəri sɝːtʃ/
A way of finding an item in a sorted list by looking at the middle and keeping only the half it could be in, again and again.
What is binary search?
Binary search finds an item in a sorted list the way you'd win a guess-my-number game: look at the middle item, and keep only the half the item could be in. Three positions do the work: low, middle and high. Every look halves what's left, so it is O(log n): about 20 looks for a million items. It only works when the list is in order.
In a sentence
- “Because the contacts were sorted by name, a binary search found the right one in about 11 looks out of 2,000.”
Level: Apprentice · More Data Structures terms at this level
Updated