概要
概要
整列済み配列に対して高速に探索する方法です。毎回半分の候補を捨てられるため O(log n) になります。
探索 / Binary Search（二分探索）
整列済み配列に対して高速に探索する方法です。毎回半分の候補を捨てられるため O(log n) になります。
目次
このページでわかること
概要
整列済み配列に対して高速に探索する方法です。毎回半分の候補を捨てられるため O(log n) になります。
考え方
low = 0, high = n - 1
while low <= high
mid = floor((low + high) / 2)
if a[mid] == target return mid
if a[mid] < target then low = mid + 1 else high = mid - 1要点
O(1)
O(log n)
O(log n)
整列済み
補足
1 回比較するごとに候補が半分になるからです。
整列されていないと左右どちらを捨てるか判断できません。
Linear Search と並べると差が際立ちます。
動きで確認
ここでは「何を比較するか」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。