이분 탐색

🚀 탐색 알고리즘으로 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$