golangで二分探索

「珠玉のプログラミング」を読んでいて、二分探索をc言語で書いてみるくだりがあったので、golangで書きなおしてみました。

二分探索はソートされている配列に対して、探索範囲を半分ずつに絞ることによってO(log N)で探索することができるアルゴリズムです。

下のコードでは、関数solveに整数の配列arrayと探索対象のtargetを渡すと、存在した場合は配列のindex、存在しない場合は-1を返します。

package main

import "fmt"

// array[0..n-1]からtargetを探す
// targetの位置をpとして
// targetがないとき、p=-1
// targetがあるとき、0<=p<=n-1 && target=array[p]
func main() {
    array := []int{1, 3, 6, 9, 100, 101}
    target := 100
    p := solve(array, target)
    fmt.Println("target index is ", p)
}

func solve(array []int, target int) int {

    // 範囲start < endを探索する
    arrayLen := len(array)
    start := 0
    end := arrayLen - 1
    var index int
    for {
        if end < start {
            return -1
        }
        index = (start + end) / 2

        if array[index] == target {
            return index
        }

        if array[index] < target {
            start = index + 1
        } else {
            end = index - 1
        }
    }
}

startとendの距離がループする毎に短くなっていくため、end < startとなるまでに探索対象が存在しない場合は終了します。

以上、golangで二分探索を書いてみた例でした。