バイナリーサーチを利用して要素を検索する - Qiita

調べたことを整理して落とし込めるためにまとめます。 Rubyを使用しています。 バイナリーサーチとは データの検索をする際に用いられる手法のことを言います。 ソート済みのデータ 同一の値が存在しない配列に入ったデータ などが対象です。 検索したい値 = A リストの中央に位置する値 = B を用意し、AがBより大きければリストの左側にある値を検索対象から除外します。 これを繰り返すことで検索にかかるコストを減らすことができます。 実際に書いたコード def binary_search(array, num) first = 0 last = array.length - 1 while first <= last center = (first + last) / 2 if num == array[center] return puts "#{num}は配列の#{center}番目に存在