めぐる式二分探索法を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)
}