Lesson 4 — Advanced
Binary Search on Answer
Ye binary search ka sabse powerful pattern hai! Jab tumhe "minimum possible value" ya "maximum possible value" dhundhni ho jismein koi condition satisfy ho, toh binary search on answer use karo. Array pe nahi, answer space pe search karte ho!
Pattern kya hai?
WHAT
Binary Search on Answer mein tum array pe nahi, balki answer space pe binary search karte ho. Agar answer = k se condition satisfy hoti hai, toh k ya chhota try karo. Nahi hoti toh bada try karo. Monotonicity honi chahiye — agar k pe ho raha hai toh k+1 pe bhi hoga (minimization mein).
WHEN
Jab question mein "minimum speed", "minimum capacity", "maximum distance", "minimum days" jaise keywords ho. Aur ek feasible(mid) function ho jo check kare ki mid pe answer possible hai ya nahi.
WHERE
Koko Eating Bananas, Capacity to Ship Packages, Split Array Largest Sum, Magnetic Force Between Balls, Minimize Max Distance to Gas Station — ye sab is pattern pe based hain.
feasible() function likho jo check kare ki given value pe answer possible hai.
Visual: Answer Space Binary Search
Answer Space: [min_possible .... max_possible]
? ?
left right
Example: Koko Eating Bananas
peedhi = [3, 6, 7, 11], h = 8 hours
Answer = eating speed k (bananas/hour)
Range: [1, 11] (min 1 banana, max 11)
k=1: 3+6+7+11 = 27 hours ? 27 > 8 ? (too slow)
k=6: 1+1+2+2 = 6 hours ? 6 <= 8 ? (possible!)
k=4: 1+2+2+3 = 8 hours ? 8 <= 8 ? (possible!)
Binary search on k:
Step 1: left=1, right=11, mid=6 ✓ feasible ? ✓ right=6
Step 2: left=1, right=6, mid=3 ✓ feasible ? ✓ left=4
Step 3: left=4, right=6, mid=5 ✓ feasible ? ✓ right=5
Step 4: left=4, right=5, mid=4 ✓ feasible ? ✓ right=4
Step 5: left=4, right=4 ✓ answer = 4 ?Example 1: Koko Eating Bananas
import math
def min_eating_speed(piles, h):
def feasible(speed):
hours = 0
for pile in piles:
hours += math.ceil(pile / speed)
return hours <= h
left, right = 1, max(piles)
while left < right:
mid = (left + right) // 2
if feasible(mid):
right = mid
else:
left = mid + 1
return left
# Usage
piles = [3, 6, 7, 11]
print(min_eating_speed(piles, 8)) # 4
piles2 = [30, 11, 23, 4, 20]
print(min_eating_speed(piles2, 5)) # 30Example 2: Capacity to Ship Packages
def ship_within_days(weights, days):
def feasible(capacity):
current_load = 0
days_needed = 1
for w in weights:
if current_load + w > capacity:
days_needed += 1
current_load = 0
current_load += w
return days_needed <= days
left, right = max(weights), sum(weights)
while left < right:
mid = (left + right) // 2
if feasible(mid):
right = mid
else:
left = mid + 1
return left
# Usage
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(ship_within_days(weights, 5)) # 15Example 3: Split Array Largest Sum
def split_array(nums, m):
def feasible(max_sum):
count = 1
current = 0
for num in nums:
if current + num > max_sum:
count += 1
current = 0
current += num
return count <= m
left, right = max(nums), sum(nums)
while left < right:
mid = (left + right) // 2
if feasible(mid):
right = mid
else:
left = mid + 1
return left
# Usage
nums = [7, 2, 5, 10, 8]
print(split_array(nums, 2)) # 18[min_possible, max_possible] se start karo.
Try it: code khud likho
Exercise
Question: Piles = [30, 11, 23, 4, 20], h = 5. Koko ko minimum kitni speed (bananas/hour) chahiye taaki wo sab piles kha sake 5 hours mein✓ Answer mein number daalo.
Question: Weights = [1, 2, 3, 4, 5], days = 3. Minimum capacity kya hai taaki sab packages 3 days mein ship ho sake✓ Answer mein number daalo.
Common mistakes
- Range galat rakhna: Answer space ka range hamesha
[min_possible, max_possible]rakhna. Jaise Koko mein min=1, max=max(piles). Range galat hoga toh answer galat aayega. - Feasible function mein galti: Feasible function mein
math.ceil(pile / speed)use karo,pile // speednahi. Integer division se wrong answer aayega. - left < right vs left <= right: Answer space mein hamesha
left < rightuse karo aurright = mid/left = mid + 1.<=se infinite loop ho sakta hai. - Binary search on array vs answer: Agar array sorted hai toh normal binary search. Agar "optimal value" dhundhni hai toh binary search on answer. Dono confuse mat karo!
Binary Search on Answer samajh aa gaya✓ Ab top problems dekhte hain jo interview mein aati hain — inpe practice karo!