Binary Search

---

TOPIC NAME: Binary Search

1. ABOUT THE TOPIC

• Binary search repeatedly cuts the search space in half to find an answer efficiently.
• It is important because it turns many O(n) searches into O(log n) solutions.
• In interviews, binary search is used not only on sorted arrays but also on monotonic answer spaces like capacity, speed, or minimum possible value.

2. KEY CONCEPTS

• Sorted Search Space: Classic binary search requires order.
• Monotonic Property: If a condition becomes true and stays true, binary search often fits.
• Lower Bound and Upper Bound: Useful when duplicates are involved.
• Mid Calculation: Use a safe formula to avoid overflow.
• Search on Answer: Binary search the result itself, not the array position.

3. COMMON PATTERNS

• Classic Binary Search: Use when searching for a target in a sorted array.
• First True or Last False: Use for boundary-finding problems.
• Search in Rotated Array: Use binary search with extra logic for sorted halves.
• Answer Space Binary Search: Use when validating a guessed answer is possible.

4. COMPLEXITY GUIDE

• Classic binary search runs in O(log n) time and O(1) space.
• Search-on-answer problems often cost O(log range * validationCost).
• When duplicates exist, be precise about whether you need exact match, first occurrence, or insertion position.

5. QUESTIONS (WITH LINKS)

EASY:

• Binary Search
  Link: https://leetcode.com/problems/binary-search/

• Search Insert Position
  Link: https://leetcode.com/problems/search-insert-position/

MEDIUM:

• Search in Rotated Sorted Array
  Link: https://leetcode.com/problems/search-in-rotated-sorted-array/

• Find Peak Element
  Link: https://leetcode.com/problems/find-peak-element/

• Koko Eating Bananas
  Link: https://leetcode.com/problems/koko-eating-bananas/

HARD:

• Median of Two Sorted Arrays
  Link: https://leetcode.com/problems/median-of-two-sorted-arrays/

6. INTERVIEW TIPS

• Always define the loop invariant before coding.
• Decide whether your answer is left, right, or a stored index after the loop.
• In answer-space problems, explain the monotonic condition clearly.
• Be careful with infinite loops caused by wrong pointer updates.

7. PRACTICE STRATEGY

• Start with direct target search.
• Then solve first/last occurrence and insertion-point problems.
• Move into rotated arrays, peak problems, and finally binary search on answers.

8. BLOG SEO META

• Title: Binary Search in DSA | Classic Search, Boundaries, and Answer Space
• Description: Learn binary search patterns for interviews, from sorted arrays and rotated arrays to lower bound, upper bound, and answer-space problems.
• Keywords: binary search DSA, answer space binary search, rotated sorted array, lower bound upper bound