Back to DSA DashboardConcept Mastery
DSA Core Concept
Binary Search
Binary Search is a divide-and-conquer search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element and halves the search space recursively.
Why It Exists
Scanning N elements sequentially takes linear O(N) time. Binary search leverages sorted properties to find elements in logarithmic O(log N) time, making it scale to billions of items.
Intuition for Beginners
“Think of finding page 300 in a book. You split the book in the middle and see page 200. Since 300 is larger, you ignore the first half of the book and repeat the process on the second half.”
Visual Explanation
Sorted Array Binary Search:
[ 10 | 20 | 30 | 40 | 50 | 60 | 70 ] Target = 60
L M R Mid = 40 (60 > 40, shift L to M + 1)
L M R Mid = 60 (Found!)Complexity Analysis
| Operation | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Search Loop | O(log N) | O(1) | Highly optimized constant space |
| Recursive Search | O(log N) | O(log N) | Call stack scales with tree depth |
Production & Real World Applications
- •Git Bisect: Logarithmic checks to find the commit that introduced a bug.
- •Database Indexes: Binary search lookups inside sorted pages.
Algorithmic Patterns
Binary Search on Answer Space
Finding the minimum or maximum threshold that satisfies a condition where options are monotonic (e.g. shipping capacity).
Defending the Design (Interview Q&A)
Q:Why does mid = (left + right) / 2 fail in some environments, and how do we fix it?
If left and right are very large numbers, adding them can exceed the integer storage limit, causing overflow. We fix this by writing: `mid = left + Math.floor((right - left) / 2)`.
Common Traps & Mistakes
- ⚠️Running on unsorted arrays (binary search requires sorted arrays).
- ⚠️Off-by-one errors in loop boundaries (e.g. writing `left < right` instead of `left <= right`).