二分探索

• 「指数的爆発」を逆手に取った探索方法
• 探索範囲を探索していくごとに半分にしていく
• つまり，1回多く調べれば，2倍の探索範囲から探し出せるようにすることで，大量のデータから効率よく探し当てることができる
• 探索対象のレコード列の長さが$n$ならば，$\log_2 n$回領域を半分にしていけば，探索すべき範囲が$1$になるので，二分探索は$O(\log_2 n)$で，効率がいい
• 探索範囲を狭める根拠が必要になる．よって，探索対象は「整列」されている必要がある
• 二分探索における「列」として配列を用いる（線形リストは使わない）
  • 何故ならば，ある範囲を決めたとき、ちょうど真ん中にあるデータに即座にアクセスできる必要があるから

🚀探索アルゴリズムとして二分探索を採用する時のデータ構造の満たす性質

1. データがソートされている
2. ある範囲を決めた時，ちょうど真ん中にあるデータに即座にアクセスできる

これを満たすデータ構造は「配列」か「二分木」

• 配列はランダムアクセス性がある
• 二分木は左右にぶら下がるノードの個数がだいたい同じだと二分探索に向いている

素朴にやる

• ループ回るごとに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$