二分探索

nこのデータが左から小さい順に並んでいるとする

まず中央のデータを見る

指定されたデータの値が中央のデータより大きければ、指定された値は中央よりも右にあることが分かる

同様に、指定されたデータの値が中央のデータより小さければ、指定されたデータの値は中央よりも左にあることが分かる

次に、半分になったデータのそのまた中央の値を見る

最初同様に、指定されたデータの値が中央の値より大きいか小さいかで探索するデータを絞る

以上を繰り返して指定されたデータの値を探索する方法

計算量はO(log n)

関連記事