Binary Search Visualizer
Visualize how binary search algorithm works step by step
Array Bar Chart
Arrays are automatically sorted for binary search
Time Complexity
Space Complexity
Characteristics:
- • Divide and Conquer: Eliminates half of the search space in each step
- • In-place: Uses constant extra space
- • Efficient: Much faster than linear search for large datasets
- • Requires sorted data: Array must be sorted beforehand
When to Use:
- • Large sorted datasets
- • When you need to search frequently
- • Performance-critical applications
- • When data is already sorted
- • When you need guaranteed O(log n) performance
When NOT to Use:
- • Unsorted arrays (use linear search instead)
- • Very small datasets (overhead not worth it)
- • When data changes frequently
- • When sorting cost is prohibitive
1. Initialize: Set left = 0, right = n-1 (array bounds).
2. Calculate Mid: mid = (left + right) / 2.
3. Compare: Check if arr[mid] equals the target.
4. Found: If equal, return mid index.
5. Narrow Range: If target < arr[mid], search left half (right = mid-1).
6. Continue: If target > arr[mid], search right half (left = mid+1).
7. Repeat: Continue until found or left > right.
8. Not Found: If left > right, return -1.
Binary Search:
- • Time: O(log n)
- • Space: O(1)
- • Requires sorted data
- • Very efficient for large data
Linear Search:
- • Time: O(n)
- • Space: O(1)
- • Works on unsorted data
- • Simple but slower
Binary search reduces the search space by half in each iteration:
• Iteration 1: Search space = n elements
• Iteration 2: Search space = n/2 elements
• Iteration 3: Search space = n/4 elements
• Iteration k: Search space = n/2^k elements
This gives us the logarithmic time complexity: O(log n)