Overview
Binary Search halves the sorted search space until the target is found or the range is empty.
Analogy
Like finding a word in a dictionary: open near the middle, decide left or right, repeat.
Step-by-step
- Start with low = 0 and high = n - 1.
- Pick mid = (low + high) // 2.
- If arr[mid] == target, return mid.
- If target < arr[mid], move high to mid - 1.
- Else move low to mid + 1. Continue while low <= high.
Visual
[1 3 5 7 9] → check 5 → go right → check 7 → found at index 3.
Common mistakes
- Forgetting to recompute mid after updating bounds.
- Using < instead of <= in the loop, skipping the last element.
- Overflow in languages where mid = (low + high) can overflow (use low + (high - low) // 2).
Practice questions
- Trace on a 7-element array with targets at both ends and an absent target.
- Return insertion index when target is absent.
- Explain why the array must be sorted; give a counterexample when it is not.
AI Wisdom