テクノロジー

2022.3.4

二分探索(バイナリサーチ)アルゴリズムについて調べてみた

二分探索の概要は、配列の中間にある値をチェックし、探索対象がそれよりも「大きい」「小さい」などで切り分けていく探索方法です。前提として探索対象のデータ群は、「昇順」や「降順」といった規則性を持っている場合のみに使用できます。

例えば、下記の昇順配列があり、配列中の20の場所を探したいとします。

[1,3,5,6,7,11,13,17,19,20,22]

イメージ図

ソースコード

func main() {
    l1 := [...]int{1, 3, 5, 6, 7, 11, 13, 17, 19, 20, 22}
    t := 20                //検索したい値
    min := 0               //最小
    mid := -1              //中間
    max := len(l1) - 1     //最大
    for min <= max {
        mid = (min + max) / 2 //中間値を取得
        if t == l1[min] {
            break
        } else if t > l1[mid] {
            min = mid + 1
        } else {
            max = mid - 1
        }
    }
    fmt.Plintln(mid)
}

こんな感じになります。
今日は二分探索（バイナリサーチ）について調べてみました。

それでは、 See you next time👉