Section: IT & Technology · Software DevelopmentDifficulty: Medium
Binary Search
USUK
An efficient algorithm that finds an item in a sorted list by halving the search space.
Also: half-interval search
Definition
Binary search is a search algorithm that works on sorted arrays by repeatedly dividing the search interval in half. Starting from the middle element, it compares the target value and eliminates half the remaining elements each iteration, achieving O(log n) time complexity. This makes it vastly more efficient than linear search for large datasets, though it requires the data to be sorted first.
Example
“Searching for a word in a sorted dictionary of 1 million entries, binary search finds it in at most 20 comparisons versus up to 1 million for linear search.”
Synonyms
- bisection search
- logarithmic search
- half-interval search
Antonyms / Opposites
- linear search
- sequential search
Images
CC-licensed · free to useLoading images…
Video
Related Terms
- algorithm
- big-o-notation
- data-structure
- recursion