はじめに
私は、基本ミニアプリを作成し学習のアウトプットを行っています。
それを備忘録として残したいと思います。
バイナリーサーチとは
配列の中のデータを検索するときに使用する手法です。配列内には同一の数値はないものとしています。
中央の値を確認し、検索したい値と大小の関係を用いて検索したい値が中央の右か左かを判断します。
それを繰り返しながら検索していく手法です。
例
8の位置が知りたい場合
[1,2,3,4,5,6,7,8,9,10]
中央値をとるので5番目の「5」が中央値となります。
8は5より大きいので、次は7~10の配列を検索します。
[7,8,9,10]
中央値をとるので2番目の「8」が中央値となり、検索が終了します。
実際のコード
1 def binary_search(array, number_of_elements, target)
2 left = 0
3 right = number_of_elements - 1
4 while left <= right
5 center = (left + right) / 2
6 if array[center] == target
7 return center
8 elsif array[center] < target
9 left = center + 1
10 else
11 right = center - 1
12 end
13 end
14 return -1
15 end
16
17 array=[1,3,5,6,9,10,13,20,26,31]
18
19 puts "検索したい数字を入力してください"
20 target = gets.to_i
21 number_of_elements = array.length
22
23 result = binary_search(array, number_of_elements, target)
24
25 if result == -1
26 puts "#{target}は配列内に存在しません"
27 else
28 puts "#{target}は配列の#{result}番目に存在します"
29 end
4~13行目で「中央の要素の定義」「検索したい値が中央の左右どちらにあるか」を確かめるコードになっています。
もしなければ14行目の「return -1」で最終的な返り値になるようにしています。
最後に
学んだことはハンズオンで行うことで定着に繋がりやすいなと実感しました！
とりあえず、「やってみる」精神を大事にしていきたいと思います！
ここまで読んでいただきありがとうございました！