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で二分探索を書いてみた例でした。