binary search はどう機能し、何を必要としますか？

Question

Accepted Answer

**Binary search** は **sorted** array で target を探す algorithm で、search range を繰り返し半分にします。各 comparison で残りの半分を除外できるため、time は **O(log n)** です。 ## 考え方 middle element を見ます。target と等しければ終了。target が小さければ left half、大きければ right half を探します。見つかるか range が empty になるまで繰り返します。 ## 例 ```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 # left half を捨てる else: hi = mid - 1 # right half を捨てる return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## Trace ```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 ``` ## Complexity - **Time:** O(log n)。**Space:** iterative なら O(1)。 ## pitfalls **input は sorted でなければなりません**。そうでないと result は意味を持ちません。`lo`/`hi` の off-by-one bug と、一部 language の integer overflow に注意します（`lo + (hi-lo)//2` を使う）。 ## なぜ重要なのか search space を半分にすることで、million-element lookup も約 20 comparisons になります。この divide-and-conquer pattern は trees、databases、多くの interview problem に再登場します。hard requirement が sorted input であることを知ると、classic subtle bug を避けられます。