囲碁における探索アルゴリズム

12239 ワード

おい、コミュニティ!
このポストでは、私はあなたと共有している私はいくつかの有名な検索アルゴリズムのために書かれたコードを囲んでいます.

線形探索

Linear search is the most basic search algorithm. What you'd do in this algorithm is basically iterate through an array until you find the desired result and return its index.

package main

import "fmt"

func linearSort(arr []int, s int) int {
    for i, v := range arr {
        if s == v {
            return i
        }
    }

    return -1
}

func main() {
    var n = []int{9, 1, 33, 21, 78, 42, 4}

    fmt.Println(linearSort(n, 78)) // 4
}

バイナリ検索

Binary search is a famous and fast searching algorithm. This algorithm requires you to provide it with an already ascendingly sorted array. This sort basically examines the middle value of the array to find out if it is equal to our target or not. If the middle value is less than the target it means the target is beyond the middle value, and if it is larger it means the target is before the middle value. And the algorithm tends to find the middle value until it matches the target.

To understand this algorithm better you can watch the video below:

package main

import "fmt"

func binarySearch(arr []int, s int) int {
    var leftPointer = 0
    var rightPointer = len(arr) - 1
    for leftPointer <= rightPointer {
        var midPointer = int((leftPointer + rightPointer) / 2)
        var midValue = arr[midPointer]

        if midValue == s {
            return midPointer
        } else if midValue < s {
            leftPointer = midPointer + 1
        } else {
            rightPointer = midPointer - 1
        }
    }

    return -1
}

func main() {
    var n = []int{2, 9, 11, 21, 22, 32, 36, 48, 76}

    fmt.Println(binarySearch(n, 32))
}

ジャンプサーチ

Jump search is an algorithm used for sorted arrays. You are going to jump by the square root of the length of the array until you find a value larger than or equal to the target. Then you have to implement a reverse linear search to determine the final result.

To understand this algorithm better you can watch the video below:

package main

import (
    "fmt"
    "math"
)

func jumpSearch(arr []int, s int) int {

    var blockSize = int(math.Sqrt(float64(len(arr))))

    var i = 0
    for {

        if arr[i] >= s {
            break
        }

        if i > len(arr) {
            break
        }

        i += blockSize
    }

    for j := i; j > 0; j-- {
        if arr[j] == s {
            return j
        }
    }

    return -1
}

func main() {
    var n = []int{2, 9, 11, 21, 22, 32, 36, 48, 76, 90}

    fmt.Println(jumpSearch(n, 76))
}