🔍
AI Sketch • मध्यम⏱️ 17 मिनट पढ़ने का समय
Binary Search Patterns
Classic Binary Search - Quick Review
Binary search हर step में search space आधा कर देता है। Sorted array में n elements में से target O(log n) time में मिल जाता है।
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
Simple - लेकिन binary search की असली ताकत sorted arrays से काफ़ी आगे है।
Search Space का Concept
Binary search तब काम करता है जब किसी range पर monotonic condition हो। "Array" का होना ज़रूरी नहीं - बस एक range [lo, hi] चाहिए और एक function जो किसी boundary पर False से True में बदले।
Search space: [lo .................. hi]
Condition: F F F F T T T T
^-- answer
🤯
Binary search पहली बार 1946 में publish हुआ, लेकिन पहला bug-free version 1962 में लिखा गया - 16 साल off-by-one errors के!
Binary Search on Answer
Array में ढूँढने की जगह answer space में search करो। सवाल पूछो: "क्या मैं result X हासिल कर सकता हूँ?" हाँ तो छोटा try करो; नहीं तो बड़ा।
Example: Koko Eating Bananas
Koko के पास n piles of bananas हैं और h hours। Minimum eating speed ढूँढो जिससे वो time पर खत्म कर सके।
def min_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum((p + mid - 1) // mid for p in piles)
if hours <= h:
hi = mid # speed works, try slower
else:
lo = mid + 1 # too slow, go faster
return lo
Answer space [1, max(piles)] है और condition monotonic है - ज़्यादा speed = कम hours।
पाठ 7 / 100% पूर्ण
Discussion
Sign in to join the discussion