dsa / dsa-arrays-strings
20 mins
DSA Module 8: O(log N) Binary Search on Monotonic Ranges
Why This Matters: Binary search divides search space in half at each step, taking O(log N) time on sorted data.
## Binary Search Algorithm
Binary search on sorted arrays.
```python
def binary_search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
MENTAL MODEL & MEMORY LAYOUT
SEARCH SPACE HALVING:
[ 1 3 5 7 9 12 15 ] (Target = 9)
▲
mid = 7 < 9 ──► Prune left half! New search space: [ 9 12 15 ] COMMON PITFALLS TO AVOID
- Using `while left < right` instead of `while left <= right` (misses single-element target check).
Binary Search Implementation
nums = [1, 3, 5, 7, 9] target = 7 # Output index 3 in O(log N) iterations
Halves search interval at mid index comparison on sorted input.
CONCEPT MASTERY CHECKPOINT
What prerequisite MUST be satisfied before running Binary Search on an array?
NEXT RECOMMENDED LESSON
DSA Module 9: Binary Trees & BST
Challenge: Find target index in sorted array using binary search.