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