最近发现不少小伙伴都对Golang很感兴趣，所以今天继续给大家介绍Golang相关的知识，本文《为什么在 Go 中的二分搜索是错误的》主要内容涉及到等等知识点，希望能帮到你！当然如果阅读本文时存在不同想法，可以在评论中表达，但是请勿使用过激的措辞~

无法弄清楚为什么 go 中的二分搜索实现不正确。 输入为 ([]int{-1, 0, 3, 5, 9, 12}, 9)

func Search(nums []int, target int) int {

    mid := len(nums) / 2

    if nums[mid] == target {
        return mid
    }
    if len(nums) >= 1 {
        if nums[mid] < target {
            return Search(nums[mid+1:], target)
        } else {
            return Search(nums[:mid], target)
        }
    }

    return -1
}

正确答案

二分查找

更新以修复无限递归

感谢@sprutex 发现该错误

func search(nums []int, target int) int {
    mid := len(nums) / 2

    if nums[mid] == target {
        return mid
    }
    if len(nums) > 1 {
        if nums[mid] < target {
            res := search(nums[mid:], target)
            if res == -1 {
                return -1
            }
            return res + mid
        } else {
            return search(nums[:mid], target)
        }
    }

    return -1
}

原始答案

请勿使用 - 搜索时包含无限递归错误 对于不在列表中的项目。

func Search(nums []int, target int) int {

    mid := len(nums) / 2

    if nums[mid] == target {
        return mid
    }
    if len(nums) >= 1 {
        if nums[mid] < target {
            return Search(nums[mid:], target) + mid
        } else {
            return Search(nums[:mid], target)
        }
    }

    return -1
}

更改的一行如下：

return 搜索(nums[mid:], 目标) + mid

本篇关于《为什么在 Go 中的二分搜索是错误的》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！