Yadda binary search ke aiki, kuma menene abin da ita ke buƙata?

Question

Accepted Answer

**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. ## Ra'ayin 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. ## Misali ```python 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 ``` ## Bincike ```text 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 ``` ## Haddalin - **Lokaci:** O(log n). **Waje:** O(1) tattalin arziki. ## Abubuwan damewa **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`). ## Me yasa ya yaka mahimmanci 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.