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))
}

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