Definition
An algorithm that quickly finds the position of a target value in a sorted array. It is very fast because it halves the search range each time.
Key Characteristics
- ✓Prerequisite: Array must be sorted
- ✓Search range halves at each step
- ✓Can find in ~20 comparisons among 1 million items
- ✓No extra memory needed (in-place)
Use Cases
Used in these scenarios:
📖
Dictionary Lookup
Like finding a word in a thick dictionary by opening the middle and moving forward/backward
🎮
Game Ranking Search
Quickly finding players with specific scores among millions of gamers
📚
Library Book Search
Like finding a book by call number in an organized library
Operations
Main operations:
Search
O(log n)Find the index of a specific value in the array. Returns -1 if not found.
Complexity
Time Complexity
Best
O(1)
Average
O(log n)
Worst
O(log n)
Space Complexity
O(1)
Understand Deeper with Visualization
See how the algorithm works through step-by-step animations and code execution.
Start Visualization