Binary search ప్రతి అడుగులో search space ను సగానికి తగ్గిస్తుంది. n ఎలిమెంట్ల sorted array లో O(log n) సమయంలో లక్ష్యాన్ని కనుగొంటుంది.
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
సరళంగా ఉంది - కానీ binary search యొక్క నిజమైన శక్తి sorted arrays కంటే చాలా దూరం వెళ్తుంది.
మీ దగ్గర ఒక పరిధిలో monotonic condition ఉన్నప్పుడు binary search పనిచేస్తుంది. "Array" ఉండాల్సిన అవసరం కూడా లేదు - మీకు [lo, hi] పరిధి మరియు ఏదో సరిహద్దు వద్ద False నుండి True కు మారే function మాత్రమే కావాలి.
Search space: [lo .................. hi]
Condition: F F F F T T T T
^-- సమాధానం
Array లో వెతకడానికి బదులు, answer space లో వెతకండి. ప్రశ్న: "నేను X ఫలితాన్ని సాధించగలనా?" అవును అయితే, చిన్నది ప్రయత్నించండి; కాదంటే, పెద్దది ప్రయత్నించండి.
Koko దగ్గర n అరటి గుట్టలు మరియు h గంటలు ఉన్నాయి. ఆమె సమయానికి పూర్తి చేయడానికి కనీస తినే వేగం కనుగొనండి.
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 # వేగం పనిచేస్తుంది, నెమ్మదిగా ప్రయత్నించు
else:
lo = mid + 1 # చాలా నెమ్మది, వేగంగా వెళ్ళు
return lo
Answer space [1, max(piles)] మరియు condition monotonic - ఎక్కువ వేగం అంటే ఎల్లప్పుడూ తక్కువ గంటలు.
సైన్ ఇన్ చర్చలో చేరండి
ఒక pivot వద్ద rotate చేసిన sorted array: [4, 5, 6, 7, 0, 1, 2]. ఒక సగం ఎల్లప్పుడూ sorted గా ఉంటుంది. ఏ సగమో నిర్ణయించడానికి mid ని lo తో పోల్చండి, తర్వాత లక్ష్యం sorted సగంలో ఉందో లేదో తనిఖీ చేయండి.
[4, 5, 6, 7, 0, 1, 2]
L M R
ఎడమ సగం [4..7] sorted గా ఉంది.
లక్ష్యం 1 [4..7] లో లేదు → కుడి వైపు వెతకండి.
Rotated sorted array [3,4,5,1,2] లో, mid=2 (విలువ 5) అయినప్పుడు ఏ సగం sorted?
మొదటి సంఘటన కనుగొనడానికి: లక్ష్యం దొరికినప్పుడు, ఆగకండి - hi = mid సెట్ చేసి ఎడమ వైపు వెతకడం కొనసాగించండి. చివరి కోసం, lo = mid + 1 సెట్ చేసి కుడి వైపు వెతకండి.
ఈ జత searches లక్ష్యం యొక్క సంఖ్యను కూడా ఇస్తుంది: last - first + 1.
రెండు పొరుగువారి కంటే పెద్ద element. Unsorted array లో కూడా binary search పనిచేస్తుంది: nums[mid] < nums[mid + 1] అయితే, peak కుడి వైపు ఉంటుంది; లేకపోతే ఎడమ వైపు. O(log n).
Rows sorted అయి ఉండి, ప్రతి row మొదటి element ముందటి row చివరి దాని కంటే పెద్దది అయితే, matrix ను m × n elements ఉన్న ఒకే sorted array గా చూడండి. Index k ను row k // n, column k % n గా మార్చండి.
x * x ≤ n అయ్యే అతిపెద్ద పూర్ణాంకం x కనుగొనండి. Search space: [0, n]. క్లాసిక్ binary search on answer.
def sqrt(n):
lo, hi = 0, n
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= n:
lo = mid + 1
else:
hi = mid - 1
return hi
"Split array largest sum" లేదా "D రోజుల్లో packages పంపే capacity" వంటి సమస్యలు చెత్త సందర్భాన్ని కనిష్టం చేయమని అడుగుతాయి. సమాధానం monotonic: capacity C పనిచేస్తే, C+1 కూడా పనిచేస్తుంది. C పై binary search.
'D రోజుల్లో Packages పంపే Capacity' కోసం, binary search యొక్క search space ఏమిటి?
lo, hi = min_possible, max_possible
while lo < hi:
mid = (lo + hi) // 2
if condition(mid):
hi = mid # mid పనిచేస్తుంది, చిన్నది ప్రయత్నించు
else:
lo = mid + 1 # mid విఫలం, పెద్దది కావాలి
return lo
మీరు మొదటి True వెతుకుతున్నారా లేదా చివరి True వెతుకుతున్నారా అనేదాన్ని బట్టి hi = mid vs lo = mid సర్దుబాటు చేయండి.
S పరిమాణ answer space పై O(n) feasibility check తో binary search యొక్క time complexity ఏమిటి?