பைனரி தேடல் வரிசைப்படுத்தப்பட்ட வரிசையில் இலக்கை தேடும் வரம்பை மீண்டும் மீண்டும் பாதியாக்குவதன் மூலம் கண்டறிகிறது. ஒவ்வொரு ஒப்பீடும் மீதமுள்ள உறுப்புகளின் பாதியை நீக்குகிறது, இது O(log n) நேரம் தருகிறது.
மத்திய உறுப்பைப் பாருங்கள். இது இலக்குக்கு சমம் என்றால், முடிந்தது. இலக்கு சிறியது என்றால், இடது பகுதியை தேடவும்; பெரியது என்றால், வலது பகுதியை தேடவும். கண்டுபிடிக்கும் வரை அல்லது வரம்பு காலியாக இருக்கும் வரை மீண்டும் செய்யவும்.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2 # middle index
if arr[mid] == target:
return mid # found it
elif arr[mid] < target:
lo = mid + 1 # discard left half
else:
hi = mid - 1 # discard right half
return -1 # not present
binary_search([1, 3, 5, 7, 9], 7) # -> 3
Search 7 in [1,3,5,7,9]
lo=0 hi=4 mid=2 -> 5 < 7 => lo=3
lo=3 hi=4 mid=3 -> 7 == 7 => return 3
உள்ளீடு வரிசைப்படுத்தப்பட்டிருக்க வேண்டும் — இல்லையெனில் முடிவுகள் அর্থहीனம். lo/hi இல் off-by-one பிழைகள் மற்றும் சில மொழிகளில் முழு எண் நிரப்பல் பற்றி எச்சரிக்கையாக இருங்கள் (lo + (hi-lo)//2 ஐ பயன்படுத்தவும்).
தேடல் வரம்பைப் பாதியாக்குவது ஒரு மில்லியன் உপাদান தேடலை ~20 ஒப்பீடுகளாக மாற்றுகிறது.
இதற்குப் பின்னால் உள்ள பிரித்து-வெல்ல முறை மரங்கள், தரவுத்தளங்கள் மற்றும் எண்ணற்ற நேர்காணல் சிக்கல்களில் மீண்டும் தோன்றுகிறது.
அதன் ஒரு கடினமான தேவையை அறிவது — வரிசைப்படுத்தப்பட்ட உள்ளீடு — உங்களை ஒரு பாரம்பரிய நுண்ணிய பிழையிலிருந்து விடுத்தறிக்கிறது.