二分探索
二分探索
- 「指数的爆発」を逆手に取った探索方法
- 探索範囲を探索していくごとに半分にしていく
- つまり,1回多く調べれば,2倍の探索範囲から探し出せるようにすることで,大量のデータから効率よく探し当てることができる
- 探索対象のレコード列の長さが$n$ならば,$\log_2 n$回領域を半分にしていけば,探索すべき範囲が$1$になるので,二分探索は$O(\log_2 n)$で,効率がいい
- 探索範囲を狭める根拠が必要になる.よって,探索対象は「整列」されている必要がある
- 二分探索における「列」として配列を用いる(線形リストは使わない)
- 何故ならば,ある範囲を決めたとき、ちょうど真ん中にあるデータに即座にアクセスできる必要があるから
🚀探索アルゴリズムとして二分探索を採用する時のデータ構造の満たす性質
- データがソートされている
- ある範囲を決めた時,ちょうど真ん中にあるデータに即座にアクセスできる
- 何故ならば,ある範囲を決めたとき、ちょうど真ん中にあるデータに即座にアクセスできる必要があるから
これを満たすデータ構造は「配列」か「二分木」
- 配列はランダムアクセス性がある
- 二分木は左右にぶら下がるノードの個数がだいたい同じだと二分探索に向いている
素朴にやる
- ループ回るごとに2回比較しているのが無駄
package main
import (
"fmt"
)
func BinarySearch(array *[]int, target int) (bool, int) {
low, high := 0, len(*array)-1
for low <= high {
middle := (low + high) / 2
if target <= (*array)[middle] {
high = middle - 1
}
if target >= (*array)[middle] {
low = middle + 1
}
}
return low == high + 2, low - 1 // 失敗しているときは low == high + 1 になっている
}
func LinearSearch(array *[]int, target int) (bool, int) {
for i := range *array {
if (*array)[i] == target {
return true, i
}
}
return false, -1
}
func main() {
array := make([]int, 10)
for i := range array {
array[i] = i
}
fmt.Println(array)
if found, _ := BinarySearch(&array, 3); found {
fmt.Println("Found!")
} else {
fmt.Println("Not Found!")
}
}
もうちょっと賢く
package main
import "fmt"
func BinarySearch(array []int, target int) (bool, int) {
n := len(array) - 1
low, high := 1, n
for low <= high {
mid := (low + high) / 2
if target < array[mid] {
high = mid - 1
} else {
low = mid + 1
}
}
pos := high
if pos == 0 {
return false, -1
} else {
return true, pos
}
}
func main() {
array := make([]int, 11)
for i := range array {
array[i] = i*i
}
if found, _ := BinarySearch(array, 25); found {
fmt.Println("Found!")
} else {
fmt.Println("Not Found!")
}
}
- 「何をしているのか」が一見するとよくわからない.こういうときはループの不変条件に注目する
【不変条件】
1. $j = 1, 2, ..., low-1$に対して$array[j] <= target$
2. $j = high + 1, high + 2, ..., n - 1, n$に対して$array[j] > target$
Author And Source
この問題について(二分探索), 我々は、より多くの情報をここで見つけました https://qiita.com/zak74702675/items/3c84a7eec2519e3cf523著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .