🔍 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
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
function binarySearchOnAnswer(nums, threshold) {
let left = 1,
right = Math.max(...nums);
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