【algorithm】線形探索法、二分探索法

はじめに

今回は探索アルゴリズムを紹介したいと思います。

探索アルゴリズムとは

探索アルゴリズム（サーチアルゴリズム）とは、大量のデータから目的のデータを見つけるときに用いられるアルゴリズムです。
探索アルゴリズムには線形探索法（リニアサーチ）と二分探索法（バイナリサーチ）があります。
それぞれ見ていきましょう。

線形探索法（リニアサーチ）

線形探索法は、先頭から順番に目的の値が見つかるまで探す単純なアルゴリズムです。
線形探索法のポイントは二つです。
・探す値が見つかったときはその配列番号（０または自然数）を使う
・探す値が見つからなかったときはマイナスの値を使う
このようなルールで考えることにします。
流れとして、配列番号を入れる変数にマイナスの値を入れて初期化しておきます。もし見つかった場合はその変数を目的のデータの配列番号を代入して更新します。目的のデータが見つかった場合はその時点で終了します。

let nums = [1, 4, 6, 0, 3, 5]
let searchNum = 3
var index = -1
for n in 0..<nums.count {
    if nums[n] == searchNum {
        index = n
        break // forを抜ける
    }
}
print("番号:", index) // 4

配列は0番から要素番号が始まるので、番号が4ということは、先頭から5番目に目的の値が存在していたということになりますね。

二分探索法（バイナリサーチ）

二分探索法は、調べる範囲を半分に絞りながら探していきます。範囲を二つ（バイナリ）に分けて探していくので、バイナリサーチと呼ばれます。
ただし、この方法が使えるのはデータがソートされている（順番に並べる）必要があります。
小さい順に値が並んだ配列を考えます。探す値を決め、データの真ん中の値を調べます。一致すればこの時点で終了です。もし、真ん中の値が探す値より小さい場合は、真ん中より左はさらに小さい値しかないので、右側だけ探せばいいことになります。これの繰り返しになります。

let nums = [1, 4, 9, 12, 14, 23, 29, 30, 100]
let searchNum = 30
var index = -1
var left = 0
var right = nums.count - 1
while left <= right {
    let middle = Int((left + right) / 2)
    if nums[middle] == searchNum {
        index = middle
        break
    } else if nums[middle] < searchNum {
        left = middle + 1
    } else if nums[middle] > searchNum {
        right = middle - 1
    }
}
print("番号:", index) // 7

探す値より真ん中の値が大きければ、それより右は探す必要がないので、右(right)を詰めます。
探す値より真ん中の値が小さければ、それよ左は探す必要がないので、左(left)を詰めます。

おわりに

今回は探索アルゴリズムを紹介しました。
次回は整列アルゴリズムを紹介したいと思います。