二分探索法
キーワード
概要
ソート済み配列から特定の値を探索するアルゴリズム。
計算量
実装
func binarySearch(A []int, key int) int {
l := 0
r := len(A) - 1
for l <= r {
c := (l + r) / 2
if A[c] == key {
return c
}
if A[c] < key {
l = c + 1
} else {
r = c - 1
}
}
return -1
}調べる範囲を半分に絞っていくので、計算量は となる。
l <= rをl < rにすると、正しく動作しないので注意。
A の中でkey未満の個数(= key未満で最大の値のインデックス)を求める場合は、以下のようにすれば良い。
func lowerBound(arr []int, key int) int {
l := 0
r := len(arr)
for l < r {
m := (l + r) / 2
if arr[m] < key {
l = m + 1
} else {
r = m
}
}
return l
}