二分探索
正式名称
Binary Search
一言でいうと
整列済みデータの探索範囲を半分ずつ絞る方法
初心者向け説明
中央の値と目的値を比較し、不要な半分を捨てながら探索範囲を狭めていく方法です。
ポイント
- 基本的に探索キーで整列済みである必要がある
- 時間計算量はO(log n)
- 配列などランダムアクセスしやすい構造と相性がよい
関連用語
関連記事
- 探索アルゴリズムとは？線形探索・二分探索・ハッシュ探索・DFS・BFSを基礎から理解しよう
🍯 はちみつメモ
二分探索 = 整列済みデータの探索範囲を半分ずつ絞る方法