Golang 二分查找

Question

Golang 二分查找

3

我正在练习一道面试算法题，现在用Go语言进行编码。目的是熟练掌握常见面试算法，同时提升自己在Go语言上的技能。我正在尝试对一个数字数组进行二分查找。

package main

import "fmt"

func main() {
    searchField := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
    searchNumber := 23

    fmt.Println("Running Program")
    fmt.Println("Searching list of numbers: ", searchField)
    fmt.Println("Searching for number: ", searchNumber)

    numFound := false
    //searchCount not working. Belongs in second returned field
    result, _ := binarySearch2(searchField, len(searchField), searchNumber, numFound)
    fmt.Println("Found! Your number is found in position: ", result)
    //fmt.Println("Your search required ", searchCount, " cycles with the Binary method.")
}

func binarySearch2(a []int, field int, search int, numFound bool) (result int, searchCount int) {
    //searchCount removed for now.
    searchCount, i := 0, 0
    for !numFound {
        searchCount++
        mid := i + (field-i)/2
        if search == a[mid] {
            numFound = true
            result = mid
            return result, searchCount
        } else if search > a[mid] {
            field++
            //i = mid + 1 causes a stack overflow
            return binarySearch2(a, field, search, numFound)
        }
        field = mid
        return binarySearch2(a, field, search, numFound)
    }
    return result, searchCount
}

我遇到的主要问题是：

1）当在列表中的数字高于我的mid搜索时，我是否真的在继续进行二进制搜索，或者已经变成了顺序搜索？我该如何解决这个问题？我已经注释掉了另一个选项，因为它会导致堆栈溢出。

2）我想添加一个步骤计数器，以查看完成搜索需要多少步。其他搜索方法也可以使用。如果我按原样打印搜索计数，它总是读取为1。这是因为我需要返回它（并且在方法中调用它），以便在标头中调用它吗？

我知道Go有简化此过程的方法。我正在努力提高我的知识和编码技能。感谢您的帮助。

- as.beaulieu

1

为什么不搜索一下？https://github.com/ZachOrr/golang-algorithms/blob/master/searching/binary-search.go - Alex Pliutau

1

可能是Go递归二分查找的重复问题。 - Dovydas Bartkevičius

6个回答

5

func BinarySearch(a []int, x int) int {
    r := -1 // not found
    start := 0
    end := len(a) - 1
    for start <= end {
        mid := (start + end) / 2
        if a[mid] == x {
            r = mid // found
            break
        } else if a[mid] < x {
            start = mid + 1
        } else if a[mid] > x {
            end = mid - 1
        }
    }
    return r
}

- blues911

2

虽然不是主题，但对于那些寻找简单二分查找的人可能会有帮助。

由于标准库没有提供这个常见功能，所以在github上有一个通用的二分查找模块：https://github.com/bbp-brieuc/binarysearch

- binary searcher

1

func BinarySearch(array []int, target int) int {
  startIndex := 0
  endIndex := len(array) - 1
  midIndex := len(array) / 2
  for startIndex <= endIndex {

    value := array[midIndex]

    if value == target {
        return midIndex
    }

    if value > target {
        endIndex = midIndex - 1
        midIndex = (startIndex + endIndex) / 2
        continue
    }

    startIndex = midIndex + 1
    midIndex = (startIndex + endIndex) / 2
}

  return -1
}

- Michael Horojanski

0

泛型类型版本！（Go 1.18）

时间复杂度：log2(n)+1

package main
import "golang.org/x/exp/constraints"

func BinarySearch[T constraints.Ordered](a []T, x T) int {
    start, mid, end := 0, 0, len(a)-1
    for start <= end {
        mid = (start + end) >> 1
        switch {
        case a[mid] > x:
            end = mid - 1
        case a[mid] < x:
            start = mid + 1
        default:
            return mid
        }
    }
    return -1
}

完整版本带有迭代计数器，请访问playground。

- Vivian K. Scott

-1

func search(nums []int, target, lo, hi int) int {


    if(lo > hi) {
        return -1
    }

    mid := lo + (hi -lo) /2

    if(nums[mid]< target){
        return search2(nums, target,mid+1, hi)
    }

    if (nums[mid]> target){
        return search2(nums, target,lo, mid -1)
    }

    return mid
 }

https://www.youtube.com/watch?v=kNkeJ3ZtgJA

- digitebs

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kaedys · Accepted Answer

您没有正确执行二分搜索。首先，您的for循环是无用的，因为条件树中的每个分支都有一个返回语句，所以它最多只能运行一次迭代。看起来您开始编写迭代版本，然后切换到递归设置，但只部分转换了。

二分搜索的思想是你有一个高和低索引，并搜索它们之间的中点。您没有这样做，而只是增加field变量并重试（这将导致您在找到该项或通过列表末尾运行时段错误之前搜索每个索引两次）。不过，在Go中，您不需要跟踪高和低索引，因为您可以根据需要简单地对搜索字段进行子片操作。

以下是一个更优雅的递归版本：

func binarySearch(a []int, search int) (result int, searchCount int) {
    mid := len(a) / 2
    switch {
    case len(a) == 0:
        result = -1 // not found
    case a[mid] > search:
        result, searchCount = binarySearch(a[:mid], search)
    case a[mid] < search:
        result, searchCount = binarySearch(a[mid+1:], search)
        if result >= 0 { // if anything but the -1 "not found" result
            result += mid + 1
        }
    default: // a[mid] == search
        result = mid // found
    }
    searchCount++
    return
}

https://play.golang.org/p/UyZ3-14VGB9