Binary Search
Binary Search is one of the most efficient searching algorithms with O(log n) time complexity. It works on sorted arrays by repeatedly dividing the search space in half, eliminating half of the remaining elements with each comparison. This divide-and-conquer approach makes it exponentially faster than linear search for large datasets.
Visualization
Interactive visualization for Binary Search
Interactive visualization with step-by-step execution
Implementation
1function binarySearch(arr: number[], target: number): number {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left <= right) {
6 const mid = Math.floor((left + right) / 2);
7 if (arr[mid] === target) return mid;
8 if (arr[mid] < target) left = mid + 1;
9 else right = mid - 1;
10 }
11
12 return -1;
13}Deep Dive
Theoretical Foundation
Binary Search is a searching algorithm that operates on a sorted or monotonic search space, repeatedly dividing it into halves to find a target value in logarithmic time O(log N). The algorithm works by comparing the target value with the middle element of the array. If the target equals the middle element, the search is successful. If the target is smaller, the algorithm continues searching in the left half; if larger, it continues in the right half. This process repeats until the element is found or the search space is exhausted. The key prerequisite is that the data structure must be sorted and allow constant-time access to any element (like arrays). Binary Search can be implemented both iteratively and recursively, with the iterative approach being more space efficient.
Complexity
Time
O(1)
O(log n)
O(log n)
Space
O(1)
Applications
Industry Use
Database indexing using B-trees and B+ trees for fast data lookup
Git bisect command to isolate faulty commits in version control
Network routing and IP address lookup in routing tables
File system directory searches and symbol tables
Gaming engines for collision detection using sorted spatial data
Machine learning hyperparameter tuning (learning rate, thresholds)
Search engines for efficient document retrieval
Library systems for quick book/resource location
Dictionary and spell-checker implementations
Competitive programming for optimization problems
Use Cases
Related Algorithms
Linear Search
Linear Search, also known as Sequential Search, is the simplest searching algorithm that checks each element in a list sequentially until the target element is found or the end is reached. Despite its O(n) time complexity, it's the only option for unsorted data and remains practical for small datasets or when simplicity is crucial.
Jump Search
Jump Search is an efficient algorithm for sorted arrays that combines the benefits of linear and binary search. Instead of checking every element (linear) or dividing the array (binary), it jumps ahead by fixed steps of √n and then performs linear search within the identified block. This approach achieves O(√n) time complexity, making it faster than linear search while being simpler than binary search for certain applications.
Interpolation Search
Interpolation Search is an improved variant of binary search specifically optimized for uniformly distributed sorted arrays. Instead of always checking the middle element, it estimates the target's position based on the target value relative to the range of values, similar to how humans search a phone book. Achieves O(log log n) average time for uniformly distributed data, significantly faster than binary search's O(log n).
Exponential Search
Combines exponential growth with binary search. Especially useful for unbounded/infinite arrays.