How fast can you find a word in a dictionary?
Binary search
How fast can you find a word in a dictionary?
Imagine you're looking for a word in a dictionary. You flip through pages, but the dictionary is sorted alphabetically.
Instead of flipping through each page, you open the dictionary in the middle and see if the word you're looking for is there. If not, you decide if it's alphabetically before or after the middle word and flip through the relevant half. You repeat this until you find the word.
Example
If the dictionary has 1024 words, you might need to flip through 10 pages (since log base 2 of 1024 is 10) to find your word.
Remember this
Binary search cuts the search area in half each time, making it much faster than flipping through the entire dictionary.
Text adapted from Wikipedia, licensed under CC BY-SA 4.0.
Related concepts
merge sort: O(n log n) always
Ever wondered why sorting your music library takes ages?
O(n log n) is the lower bound for comparison-based sorting
Ever wonder why sorting can't be faster than a certain point?
Dijkstra's algorithm
Dijkstra's algorithm time complexity: O((V+E) log V)
Best, worst and average case
Quicksort's average time complexity is O(n log n)
Graph (abstract data type)
Time complexity of BFS and DFS: O(V + E)
Hash table
Hash table lookup: O(1) average time complexity
Swipe through 100 ML concepts daily
Open Pocket Polymath