Binary search tana neman manufa a cikin jeri da aka tsara ta hanyar ɓoyawa da ɓoyawa sau-sau. Kowane bambantawa tana kawar da rabin sauran abubuwan, tana ba O(log n) lokaci.
Duba zaɓen tsakiya. Idan yayi daidai da manufa, gida. Idan manufa ta ƙanƙanta, bincika rabin hagu; idan ta fi girma, bincika rabin dama. Maimaita har sai an samu ko ranar ba ɗan waje.
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
Shigarwar dole ne a tsara — in ba haka ba sakamakon ba su da ma'ana. Jingina gamewar-daya kuskure a lo/hi da ƙetare integer a wasu harsuna (yi amfani da lo + (hi-lo)//2).
Rabon sararin inqila'i yana juyar da neman kwafi miliyan-abun zuwa ~20 bambantawa.
Tsarin rabu-da-saurari a bayansa ya nuna shi a bishiyoyi, na data, da bakin haɗi na mafita.
Sanin ainihin bukatunsa guda - shigarwar da aka tsara - ana iyale dari dabam-dabam.
Ɗakin karatu na tambayoyin hira na IT tare da amsoshi cikakke — daga Junior zuwa Senior.
Ba da Gudummawa