Goでのアルゴリズムクイックリファレンス第2版(二分探索)

Goに慣れるためとアルゴリズムの復習の為に週1ぐらいで更新していきます。アルゴリズムクイックリファレンス 第2版を読んで各種アルゴリズムをGoで実装して行きます。

前回: Goでのアルゴリズムクイックリファレンス第2版(マージソート)

今回は二分探索

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく

計算時間はO(log2n)となる

package main

import (
	"fmt"
)

func search(a *[]int, t int) bool {
	low := 0
	high := len(*a) - 1
	for low <= high {
		mid := (low + high) / 2
		if t < (*a)[mid] {
			high = mid - 1
		} else if t > (*a)[mid] {
			low = mid + 1
		} else {
			return true
		}
	}
	return false
}

func main() {
	a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println(a)
	fmt.Printf("2:%t\n", search(&a, 2))
	fmt.Println(a)
	fmt.Printf("12:%t\n", search(&a, 12))
}

次回はハッシュに基づいた探索の予定です。