Binary Search
EasyBinary Search is an efficient algorithm for finding an item from a sorted list by repeatedly dividing the search interval in half. It requires the input to be sorted.
Time Complexity
O(log n)Space Complexity
O(1)Category
Searching
Introduction to Binary Search
Binary Search is one of the most important search algorithms, providing O(log n) search time for sorted arrays. It's much faster than linear search and forms the foundation for many advanced data structures and algorithms.
How It Works
The algorithm works by repeatedly dividing the search space in half:
1. Start with the middle element of the sorted array
2. If it matches the target, return the index
3. If target is smaller, search the left half
4. If target is larger, search the right half
5. Repeat until found or search space is exhausted
Algorithm Complexity
Prerequisites
Best and Worst Cases
Advantages
1. Very efficient - O(log n) time complexity
2. Space efficient - O(1) for iterative version
3. Predictable performance
4. Works on large datasets
5. Can be used for range queries
Disadvantages
1. Requires sorted input
2. Sorting has O(n log n) cost
3. Slower on small datasets than linear search
4. Not suitable for linked lists without random access
When to Use
Variations
1. **Recursive Binary Search**: Using recursion instead of iteration
2. **Exponential Search**: Find range first, then binary search
3. **Interpolation Search**: Estimates position based on value
4. **Lower/Upper Bound**: Finding first/last occurrence
Real-world Applications
Key Takeaways
- Works only on sorted arrays
- Eliminates half elements per iteration
- Logarithmic time complexity
- Space efficient
- Two-pointer approach
- Fast for large datasets
Implementation
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}