Utafutaji wa binary hupata lengo katika safu iliyoagizwa kwa nusu mara kwa mara ya masafa ya utafutaji. Kila kulinganisha kuondoa nusu ya vipengele vilivyobaki, ikitoa O(log n) wakati.
Tazama kipengele cha katikati. Ikiwa ni sawa na lengo, nakamilika. Ikiwa lengo ni ndogo, tafuta nusu ya kushoto; ikiwa ni kubwa, tafuta nusu ya kulia. Rudia hadi kupata au masafa yatakuwa tupu.
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
Ingizo lazima iwe iliyoagizwa — vinginevyo matokeo hayaina maana. Jinga off-by-one matatizo katika lo/hi na kuzidi namba kamili katika lugha nyingine (tumia lo + (hi-lo)//2).
Kukatalia nusu ya nafasi ya utafutaji kubadili utafutaji wa kipengele cha milioni katika ~20 kulinganisha.
Mfumo wa mgawanyiko-na-kushinda nyuma yake unaonekea mara kwa mara katika miti, hifadhidata, na matatizo mengi ya mahojiano.
Kujua mahitaji yake moja magumu — ingizo lililoagizwa — hukuzuia kutoka kwa kosa la kawaida la sumu.