Hogyan működik a bináris keresés, és mit igényel?

Question

Accepted Answer

**Binary search** egy célt talál egy **rendezett** tömbben a keresési tartomány ismételt felezésével. Minden összehasonlítás kiküszöböli a hátralévő elemek felét, ami **O(log n)** időt ad. ## Az ötlet Nézzük meg a középső elemet. Ha egyenlő a céllal, kész. Ha a cél kisebb, keresünk a bal felében; ha nagyobb, a jobb felében. Ismételjük, amíg meg nem találjuk vagy a tartomány üres nem lesz. ## Példa ```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 ``` ## Nyomkövetés ```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 ``` ## Bonyolultság - **Idő:** O(log n). **Tér:** O(1) iteratív. ## Csapdák **A bemenet rendezettnek kell lennie** — ellenkező esetben az eredmények értelmetlen. Vigyázzon az egygyel elcsúszott hibákra a `lo`/`hi` és egész szám túlcsordulásra bizonyos nyelvekben (használjon `lo + (hi-lo)//2`). ## Miért fontos A keresési tér felezése egy milliós elemű keresést ~20 összehasonlításra redukál. A mögötte lévő osztás-és-urasd minta fák, adatbázisok és számtalan interjúkérdés során jelenik meg újra. Ennek egyetlen kemény követelményét — rendezett bemenetet — ismerve megóvja magát egy klasszikus, finom hiba elől.