めぐる式二分探索法をGoで実装する

簡単に調べて、Qiitaで見つからなかったので

参考文献

• めぐる式二分探索
• めぐる式二分探索の紹介

実装

package main

import (
    "math"
)

var a = [10]int{1, 14, 32, 51, 51, 51, 243, 419, 750, 910}

func abs(x int) int {
    return int(math.Abs(float64(x)))
}

func isOK(index, key int) bool {
    return a[index] >= key
}

func binarySearch(key int) int {
    ng := -1
    ok := len(a)

    for abs(ok-ng) > 1 {
        mid := (ok + ng) / 2

        if isOK(mid, key) {
            ok = mid
        } else {
            ng = mid
        }
    }
    return ok
}

func main() {
}

テスト

// データ
// var a = [10]int{1, 14, 32, 51, 51, 51, 243, 419, 750, 910}

func TestBinarySearch(t *testing.T) {
    // 範囲外（左端) 気になるなら期待値は -1 であるように実装を変えてもいいかも
    got := binarySearch(0)
    want := 0
    if got != want {
        t.Errorf("binarySearch() = %d, want %d", got, want)
    }
    // 範囲外（右端)
    got = binarySearch(911)
    want = 10
    if got != want {
        t.Errorf("binarySearch() = %d, want %d", got, want)
    }
    // 13が以上が条件を満たす。最小のindexは a[1] = 14 なので 1
    got = binarySearch(13)
    want = 1
    if got != want {
        t.Errorf("binarySearch() = %d, want %d", got, want)
    }
    // 14が以上が条件を満たす。最小のindexは a[1] = 14 なので 1
    got = binarySearch(14)
    want = 1
    if got != want {
        t.Errorf("binarySearch() = %d, want %d", got, want)
    }
    // 15が以上が条件を満たす。最小のindexは a[2] = 32 なので 2
    got = binarySearch(15)
    want = 2
    if got != want {
        t.Errorf("binarySearch() = %d, want %d", got, want)
    }
    // 51が以上が条件を満たす。a[x] = 51 な xの中で、最小のindexは 3
    got = binarySearch(51)
    want = 3
    if got != want {
        t.Errorf("binarySearch() = %d, want %d", got, want)
    }
}

付録: データを外だししたくない人向け

package main

import (
    "math"
)

func abs(x int) int {
    return int(math.Abs(float64(x)))
}

func isOK(a *[]int, index, key int) bool {
    return (*a)[index] >= key
}

func binarySearch(a *[]int, key int) int {
    ng := -1
    ok := len(*a)

    for abs(ok-ng) > 1 {
        mid := (ok + ng) / 2

        if isOK(a, mid, key) {
            ok = mid
        } else {
            ng = mid
        }
    }
    return ok
}

func main() {
    var a = []int{1, 14, 32, 51, 51, 51, 243, 419, 750, 910}
    println(binarySearch(&a, 51) == 3)
}