Kaip veikia dvejetainė paieška ir ko ji reikalauja?

Question

Accepted Answer

**Dvejetainė paieška** randa taikinį **rūšiuotame** masyve pakartotinai perpus sumažindama paieškos diapazoną. Kiekvienas palyginimas pašalina pusę likusių elementų, suteikdamas **O(log n)** laiką. ## Idėja Pažvelk į vidurinį elementą. Jei jis lygus tikslui, atlikta. Jei tikslas mažesnis, paieškoti kairėje pusėje; jei didesnis, paieškoti dešinėje pusėje. Kartok, kol raši arba diapazonas tuščias. ## Pavyzdys ```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 ``` ## Pėdsakas ```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 ``` ## Sudėtingumas - **Laikas:** O(log n). **Vieta:** O(1) iteracinė. ## Spąstai **Įvestis turi būti rūšiuota** — priešingu atveju rezultatai yra beprasmiai. Saugokitės off-by-one klaidų `lo`/`hi` ir sveiko skaičiaus perpildymo kai kuriose kalbose (naudokite `lo + (hi-lo)//2`). ## Kodėl tai svarbu Perpus sumažinimas paieškos erdvės pamėgdžia milijono elementų paiešką į maždaug 20 palyginimų. Dalinimo ir užkariaujimo modelis, kuris yra jos pagrindas, vėl pasirodo medžiuose, duomenų bazėse ir daugybėje pokalbio problemų. Žinojimas apie jos vienintelį griežtą reikalavimą — rūšiuotą įvestį — jus saugo nuo klasikinio subtilaus klaido.