Chapter 10: DSA Binary Search
DSA Binary Search – Let’s understand this topic like I’m sitting next to you with a notebook, explaining slowly, clearly, with lots of visuals in words, multiple examples, common mistakes, code in different styles, and real interview context.
What is Binary Search?
Binary Search is one of the most important and most frequently asked searching algorithms in DSA.
Core idea in one simple sentence:
If the array is sorted, we can eliminate half of the remaining elements with every single comparison.
Instead of checking every element one by one (like Linear Search), we repeatedly divide the search space in half — that’s why it’s called binary (two parts).
This makes it extremely fast compared to linear search when the data is large.
Real-life analogy everyone understands
Imagine you are trying to find a word in a dictionary (which is sorted alphabetically).
Do you start from page 1 and check every word one by one? No!
You do something smart:
- Open roughly in the middle
- If the word you want is before the middle word → search only left half
- If the word is after → search only right half
- Repeat the process on the chosen half
- Very quickly you narrow it down to one page, then one word
That’s exactly how binary search works!
Important Prerequisite
The array / list must be sorted (ascending or descending). If it’s not sorted → binary search cannot be used.
Step-by-step example (very detailed)
Sorted array: [2, 7, 11, 15, 19, 23, 28, 34, 41, 56, 72, 91]
We want to find 23.
Initial search space: index 0 to 11
Step 1 middle = (0 + 11) // 2 = 5 arr[5] = 23 → Found immediately! (lucky case)
But let’s do a more typical case — find 41
Step 1 low = 0, high = 11 mid = (0+11)//2 = 5 arr[5] = 23 41 > 23 → search right half Now low = 6, high = 11
Step 2 mid = (6+11)//2 = 8 arr[8] = 41 → Found at index 8
Another example — find 10 (not present)
Step 1 mid = 5 → 23 10 < 23 → left half → low=0, high=4
Step 2 mid = (0+4)//2 = 2 arr[2] = 11 10 < 11 → left → low=0, high=1
Step 3 mid = (0+1)//2 = 0 arr[0] = 2 10 > 2 → right → low=1, high=1
Step 4 mid = 1 arr[1] = 7 10 > 7 → low = 2 Now low > high → not found
Binary Search Code – Most Common Interview Style (Python)
1. Classic Iterative Version (most preferred in interviews)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
def binary_search(arr, target): low = 0 high = len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] == target: return mid # found! elif arr[mid] < target: low = mid + 1 # search right half else: high = mid - 1 # search left half return -1 # not found # Example usage numbers = [2, 7, 11, 15, 19, 23, 28, 34, 41, 56, 72, 91] print(binary_search(numbers, 23)) # Output: 5 print(binary_search(numbers, 41)) # Output: 8 print(binary_search(numbers, 10)) # Output: -1 |
2. Recursive Version (also asked sometimes)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
def binary_search_recursive(arr, target, low, high): if low > high: return -1 mid = (low + high) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search_recursive(arr, target, mid + 1, high) else: return binary_search_recursive(arr, target, low, mid - 1) # Wrapper def find(arr, target): return binary_search_recursive(arr, target, 0, len(arr)-1) |
Very Important – Time Complexity (must know perfectly)
| Case | Time Complexity | How many comparisons? |
|---|---|---|
| Best Case | O(1) | Target is in the middle |
| Average Case | O(log n) | |
| Worst Case | O(log n) | Target at end or not present |
| Space Complexity | O(1) iterative O(log n) recursive (call stack) |
Comparison table – Linear vs Binary
| Elements (n) | Linear Search (worst) | Binary Search (worst) |
|---|---|---|
| 100 | 100 comparisons | ~7 comparisons |
| 1,000 | 1,000 | ~10 |
| 1,000,000 | 1 million | ~20 |
| 1 billion | 1 billion | ~30 |
This is why binary search is magical when data is large and sorted.
Common Variations Asked in Interviews
- Find first occurrence of a number (when duplicates exist)
- Find last occurrence of a number
- Find floor / ceiling of a number
- Find the smallest number ≥ target
- Search in rotated sorted array
- Find peak element
- Binary search on answer (very important pattern)
- Find minimum in rotated sorted array
Common Mistakes People Make (interviewers watch for these)
- Writing low < high instead of low <= high → misses the last element
- Not handling duplicates when needed
- Integer overflow when calculating mid → better to write mid = low + (high – low) // 2
- Forgetting to update low/high correctly
- Trying to use binary search on unsorted data
When to use Binary Search (real decision guide)
Use Binary Search when:
- Array is sorted (or can be sorted)
- You need to find position / existence / count
- Data size is large (n ≥ 1000)
- You are doing multiple searches (sort once → binary many times)
Don’t use when:
- Array is unsorted and small → linear search is simpler
- You need to find min/max → just one pass
- You have hash-based lookup possible (O(1) average)
Summary – Binary Search in one line each
- Requires sorted array
- Repeatedly divides search space in half
- Time complexity O(log n) – extremely fast
- Very common in interviews (both easy and hard variations)
- Basis for many advanced problems (binary search on answer, rotated array, etc.)
- One of the first algorithms that shows power of logarithmic time
Would you like to continue with any of these next?
Very popular follow-up topics:
- First and last occurrence using binary search
- Binary search on rotated sorted array
- Binary search on answer pattern (very important)
- Lower bound / upper bound implementation
- Common LeetCode-style binary search questions
- How to avoid integer overflow in mid calculation
Just tell me which one you want next — I’ll explain it in the same detailed, human-teacher style! 😊
