探索アルゴリズムについて
- 線形探索（リニアサーチとは）と二分探索（バイナリーサーチ）の違い
1.線形探索（リニアサーチとは）と二分探索（バイナリーサーチ）の違い
線形探索とは先頭から順に配列を検索する方法。データーに規則性がない場合有効だけれど、計算時間がかかる。 二分探索とはデータが昇順で並んでいた場合、最初に真ん中に位置するデータと比較する。そうすることでどちらか一方のデータは計算しなくてよくなる。
例えば以下のような配列があって３を探したいとする。
[1, 3, 5, 7, 9, 11]
真ん中の数字は6なので、左側にあることがわかる。
2.線形探索のコード
def linear_search(arr, value)
arr.each_with_index do |num, index|
return index if num == value
end
return nil
end
これわざわざ名前つける必要あるのかってかんじです。
3.二分探索のコード
def binary_search(arr, n)
arr.sort!
min = 0
max = (arr.length) - 1
while true
mid = (min + max) / 2
if arr[mid] > n
max = mid
elsif arr[mid] < n
min = mid
elsif arr[mid] == n
return mid
else
return nil
end
end
end
ちなみにテストも見よう見まねで書いた。
describe "#binary" do
it "could't find value in array" do
expect(binary_search([1, 3, 5, 9, 11, 13, 15, 17, 19, 21, 23], 0)).to eq (nil)
end
it "works with sorted array" do
expect(binary_search([1, 3, 5, 9, 11, 13, 15, 17, 19, 21, 23], 9)).to eq (3)
end
it "works with unsorted array" do
expect(binary_search([15, 38, 325, 19, 211, 143, 125, 17, 19, 21, 230, 100], 21)).to eq (9)
end
end
一番目のテストで引っかかった。。。終了条件書いていなかった。
describe "#binary" do
it "could't find value in array" do
expect(binary_search([1, 3, 5, 9, 11, 13, 15, 17, 19, 21, 23], 0)).to eq (nil)
end
end
見つからなかった場合のケースです。
ようは見つからない場合どういう条件でnilを返すかを書くことが必要でした。。 ということで、見つからない時というのはどういうときかで考えると、「二分割し続けた挙句のはてに二分割の基点となるmidの値が0以下になるか,arrayの個数以上になる」とシンプルにここで切れるようにしました。
def binary_search(arr, n)
arr.sort!
min = 0
max = (arr.length) - 1
while true
mid = (min + max) / 2
if arr[mid] > n
max = mid
elsif arr[mid] < n
min = mid
elsif arr[mid] == n
return mid
elsif mid <= 0 || mid > arr.length
return nil
end
end
end
ここでまた無限ループにはまる。 上のプログラムでダメなのは、見つからない場合にループを抜けるための条件が一番下にあること。 これではnが小さい場合に二分割するというif分の二番目{ elsif arr[mid] < n }こいつに当てはまるので一生ここにハマり続けます。
def binary_search(arr, n)
arr.sort!
p arr
min = 0
max = (arr.length) - 1
while true
mid = (min + max) / 2
if mid <= 0 || mid > arr.length
return nil
elsif arr[mid] > n
max = mid
elsif arr[mid] < n
min = mid
elsif arr[mid] == n
return mid
end
end
end
