二分探索

デジタル大辞泉

にぶん‐たんさく【二分探索】

読み方：にぶんたんさく

《binary search》データ検索の手法の一。ソートされたデータ列から目的とするデータを検索する際、まずデータ列の中央の値と大小比較をし、目的とするデータがどちらにあるかを判断する。この作業を、目的のデータがあるとされた半分のデータ列に対して繰り返し行うことにより、目的とするデータを検索する。二分検索。バイナリーサーチ。

ウィキペディア

二分探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/03 08:05 UTC 版)

探索 > 二分探索

二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

概要

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。

n個のデータがある場合、時間計算量は${\displaystyle O(\log _{2}n)}$