π Binary Search
One-line summary: Repeatedly halve the search space by comparing the middle element β O(log n) on any sorted or monotonic space.
π― Core Conceptsβ
What is Binary Search?β
Binary search is a divide-and-conquer algorithm that efficiently finds a target value in a sorted array by repeatedly dividing the search space in half.
How Binary Search Worksβ
- If
arr[mid] > targetβ Search left half (right = mid - 1)
- Repeat until found or search space exhausted
Key Insightsβ
- Efficiency: Each comparison eliminates half the remaining search space
- Prerequisite: Array must be sorted (or have some monotonic property)
- Logarithmic: Reduces n elements to 1 in ~logβ(n) steps
Binary Search Variantsβ
-
Standard Search: Find exact target in sorted array
-
First/Last Occurrence: Find boundaries of duplicate elements
-
Rotated Arrays: Search in rotated sorted arrays
-
Peak Finding: Find local maxima in mountain arrays
-
Binary Search on Answer: Find optimal value in solution space
When to Use Binary Search?β
β Perfect for:
-
Sorted arrays with target search
-
"Find minimum/maximum value that satisfies condition" problems
-
Rotated or mountain arrays
-
Optimization problems with monotonic solution space
-
**Range queri
Enhanced Visualizationβ
The enhanced animation above demonstrates:
- Smooth pointer movements showing low, high, and mid pointer transitions
- Visual discard regions highlighting eliminated search space
- Step-by-step comparison logic with detailed phase descriptions
- Real-time complexity analysis showing O(log n) efficiency
- Interactive elements with glow effects and status indicatorsdata (unless you can sort first)
- Small datasets (linear search might be faster)
- When you need to find all occurrences efficiently
π Visual Learningβ
β‘ Time & Space Complexityβ
| Rotated Array Search | O(log n) | O(1) | Handle rotation with pivot |
| Peak Finding | O(log n) | O(1) | Find local maxima | | Binary Search on Answer | O(n log W) | O(1) | W = search space range | | 2D Matrix Search | O(log(mΓn)) | O(1) | Treat as 1D sorted array |
Key Insight: Binary search achieves logarithmic time by eliminating half the search space in each iteration.
π§ Essential Patterns & Templatesβ
function binarySearch(arr, target) {
let left = 0,
right = arr.length - 1;
while (left <= right) {
// Prevent integer overflow
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) {
return mid; // Found target
} else if (arr[mid] < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return -1; // Target not found
}
// Time: O(log n), Space: O(1)
// Use case: Find exact target in sorted array
2οΈβ£ First/Last Occurrence - Find Boundariesβ
function findFirstOccurrence(arr, target) {
let left = 0,
right = arr.length - 1;
let result = -1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) {
result = mid;
right = mid - 1; // Continue searching left for first occurrence
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
function findLastOccurrence(arr, target) {
let left = 0,
right = arr.length - 1;
let result = -1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) {
result = mid;
left = mid + 1; // Continue searching right for last occurrence
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// Time: O(log n), Space: O(1)
// Use case: Find range of duplicate elements
3οΈβ£ Binary Search on Answer - Optimization Problemsβ
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (isFeasible(nums, mid, threshold)) {
right = mid; // Try smaller values
} else {
left = mid + 1; // Need larger values
}
}
return left;
}
function isFeasible(nums, divisor, threshold) {
let sum = 0;
for (const num of nums) {
sum += Math.ceil(num / divisor);
}
return sum <= threshold;
}
// Time: O(n log W) where W is the search range
// Use case: "Find minimum X such that condition is satisfied"
4οΈβ£ Search in Rotated Sorted Arrayβ
function searchRotated(nums, target) {
let left = 0,
right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
// Determine which half is sorted
if (nums[left] <= nums[mid]) {
// Left half is sorted
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // Target in left half
} else {
left = mid + 1; // Target in right half
}
} else {
// Right half is sorted
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // Target in right half
} else {
right = mid - 1; // Target in left half
}
}
}
return -1;
}
// Time: O(log n), Space: O(1)
// Use case: Search in rotated sorted arrays
5οΈβ£ Search Insert Positionβ
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
}
}
// Time: O(log n), Space: O(1)
// Use case: Find insertion point for maintaining sorted order
β οΈ Common Pitfalls & How to Avoid Themβ
const mid = Math.floor((left + right) / 2); // Could overflow
// β
Safe approach - always use this
const mid = left + Math.floor((right - left) / 2);
// β Wrong boundary conditions
while (left < right) { // Missing equal case
// ... might miss exact match
}
// ... handles all cases including when left === right
}
// β
Correct for "find minimum X" problems
while (left < right) {
// ... converges to single answer
}
π« Infinite Loopsβ
// β Wrong - can cause infinite loop
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (condition) {
left = mid; // Should be mid + 1
} else {
right = mid - 1;
}
}
// β
Correct - ensure progress
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (condition) {
right = mid;
} else {
left = mid + 1;
}
}
π« Wrong Search Spaceβ
// β Wrong - not considering all possibilities
let left = 1,
right = nums.length; // Missing 0 or length?
// β
Correct - think about valid range
let left = 0,
right = nums.length - 1; // For array indices
// OR
let left = 1,
right = maxPossibleValue; // For answer space
π« Non-Monotonic Feasible Functionβ
// Binary search on answer requires monotonic property:
// If feasible(x) is true, then feasible(x+1) should also be true
// OR if feasible(x) is false, then feasible(x-1) should also be false
// β Wrong - feasible function not monotonic
function feasible(x) {
return someComplexCondition(x); // Random true/false
}
// β
Correct - monotonic feasible function
function feasible(capacity) {
return canShipWithCapacity(capacity); // Larger capacity = always feasible
}
π‘ Pro Tipsβ
- Draw the search space - visualize what you're searching
- Test boundary conditions - empty array, single element, target at edges
- Verify monotonic property for binary search on answer
- Use descriptive variable names -
left,right,midare clear - Consider edge cases - duplicates, rotated arrays, negative numbers
Practice Problemsβ
π Related Topicsβ
- Dynamic Programming β Binary search can optimize DP solutions
- Divide and Conquer β Binary search is a classic D&C algorithm
π― Quick Interview Prep Checklistβ
- Master the standard binary search template
- Understand first/last occurrence patterns
- Practice binary search on answer problems
- Know how to handle rotated sorted arrays
- Comfortable with 2D matrix search
- Understand when binary search applies
- Practice peak finding algorithms
- Know common pitfalls and edge cases
β Back to Home Β· Β© sparshjaswal