Golang中二分查找问题的解决方法

Golang中二分查找问题的解决方法 我们编写的代码如下：

package main
import "fmt"

func binarySearch(search int, list []int) int {

    low := 0
    high := len(list) - 1

    for low <= high {
        middle := (low + high) / 2

        if list[middle] < search {
            low = middle + 1
        } else {
            high = middle - 1
        }
    }

    if low == len(list) || list[low] != search {
        return 0
    }

    return low
}
func main() {
    var n int
    _, err := fmt.Scanln(&n)
    if err != nil || n < 0 {
        return
    }
    s := make([]int, n)
    for i := range s {
        fmt.Scanln(&s[i])
    }
    var n1 int
    fmt.Scanln(&n1)
    fmt.Println(binarySearch(n1, s))
}

运行结果不符合预期。


更多关于Golang中二分查找问题的解决方法的实战教程也可以访问 https://www.itying.com/category-94-b0.html

3 回复

找到值时，减小 high 并继续搜索。

更多关于Golang中二分查找问题的解决方法的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


问题在将返回值从0改为-1后得到解决。谢谢。

你的二分查找实现存在逻辑问题。主要问题在于当 list[middle] == search 时，代码会进入 else 分支将 high 设置为 middle - 1，这会导致错过匹配项。以下是修正后的代码：

package main
import "fmt"

func binarySearch(search int, list []int) int {
    low := 0
    high := len(list) - 1

    for low <= high {
        middle := low + (high-low)/2  // 避免整数溢出

        if list[middle] == search {
            return middle  // 找到目标，直接返回索引
        } else if list[middle] < search {
            low = middle + 1
        } else {
            high = middle - 1
        }
    }
    
    return -1  // 未找到返回-1
}

func main() {
    var n int
    _, err := fmt.Scanln(&n)
    if err != nil || n < 0 {
        return
    }
    
    s := make([]int, n)
    for i := range s {
        fmt.Scanln(&s[i])
    }
    
    var target int
    fmt.Scanln(&target)
    
    result := binarySearch(target, s)
    fmt.Println(result)
}

关键修改：

  1. 添加了 list[middle] == search 的判断条件，找到目标时直接返回索引
  2. 使用 low + (high-low)/2 计算中间索引，避免 (low+high) 可能导致的整数溢出
  3. 未找到时返回 -1 作为标准错误指示

示例运行：

输入：
5
1
3
5
7
9
5
输出：
2

这个实现正确处理了三种情况：

  • 中间值等于目标：返回索引
  • 中间值小于目标：搜索右半部分
  • 中间值大于目标：搜索左半部分
回到顶部