Binary Search (Divide & Conquer)
Efficient search algorithm for sorted arrays using divide-and-conquer. At each step, eliminate half of remaining elements by comparing target with middle element. One of the most fundamental algorithms in computer science with O(log n) time complexity.
Visualization
Interactive visualization for Binary Search (Divide & Conquer)
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
8 if (arr[mid] === target) return mid;
9 if (arr[mid] < target) left = mid + 1;
10 else right = mid - 1;
11 }
12
13 return -1;
14}
15
16// Recursive version
17function binarySearchRecursive(arr: number[], target: number, left = 0, right = arr.length - 1): number {
18 if (left > right) return -1;
19
20 const mid = Math.floor((left + right) / 2);
21
22 if (arr[mid] === target) return mid;
23 if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
24 return binarySearchRecursive(arr, target, left, mid - 1);
25}Deep Dive
Theoretical Foundation
Binary search repeatedly divides search space in half. By comparing target with middle element, we determine which half contains the target (if present). This halving process continues until element is found or search space is empty. The logarithmic complexity comes from halving: log₂(n) divisions needed.
Complexity
Time
O(1)
O(log n)
O(log n)
Space
O(1) iterative, O(log n) recursive
Applications
Industry Use
Database indexing and query optimization
Dictionary and spell-checker lookups
Finding insertion point in sorted lists
Debugging (finding first/last occurrence)
Game development (AI decision trees)
Scientific computing (root finding)
Library search systems
Use Cases
Related Algorithms
Merge Sort (Divide & Conquer Paradigm)
Classic divide-and-conquer sorting algorithm that recursively divides array into halves until single elements, then merges sorted subarrays. Invented by John von Neumann in 1945, it's one of the most efficient general-purpose sorting algorithms with guaranteed O(n log n) performance. The algorithm perfectly demonstrates the divide-and-conquer paradigm: divide problem, solve subproblems recursively, combine solutions.
Closest Pair of Points
Find two points with minimum Euclidean distance among n points in 2D plane using divide-and-conquer. Naive O(n²) approach checks all pairs; divide-and-conquer achieves O(n log n) by recursively finding closest pairs in left/right halves and checking split pairs efficiently.
Karatsuba Multiplication
Fast multiplication algorithm for large integers using divide-and-conquer. Discovered by Anatoly Karatsuba in 1960, it was the first algorithm to demonstrate multiplication can be done faster than O(n²). Reduces three recursive multiplications instead of four, achieving O(n^log₂3) ≈ O(n^1.585) complexity.
Closest Pair of Points
Find two closest points in 2D plane. Divide-and-conquer approach achieves O(n log n). Classic algorithm demonstrating geometric divide-and-conquer.