Go 中的二分搜索 - 到底为什么这是不正确的

Question

无法弄清楚为什么二分搜索在 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
}

Answer 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 Search(nums[mid:], target) + mid