英文:
Binary Search in Go - why the heck is this incorrect
问题
无法弄清楚为什么这个错误的二分查找实现在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
}
英文:
Cant figure out why the heck is this incorrect implementation of Binary Search in go.
Input is ([]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
}
答案1
得分: 6
二分查找
更新以修复无限递归
感谢 @sprutex 发现了这个 bug
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
}
原始答案
不要使用 - 在搜索不在列表中的项时会出现无限递归 bug。
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
英文:
Binary Search
Updated to fix infinite recursion
Thanks @sprutex for finding the bug
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
}
Original answer
DO NOT USE - contains infinite recursion bug when searching
for an item not in the list.
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
}
The one line that was changed is the following:
return Search(nums[mid:], target) + mid
答案2
得分: 0
假设你的切片是 nums=[5,12,17,20,30,39,55,67]。你的目标数字是55。当你在代码行 return Search(nums[mid:], target) 中对数组的右侧进行递归调用时，新的切片是 nums=[30,39,55,67]。在原始切片中，55的索引是6，但在新的切片中，它是2。这就是为什么你没有得到正确的答案。
当你从现有切片创建一个新的切片时，元素的索引不反映旧切片。为了弥补这一点，在选择切片的右侧进行二分查找时，你需要加上当前的 mid。
英文:
Lets say, your slice is nums=[5,12,17,20,30,39,55,67]. Your target number is 55. When you make a recursive call on the right side of the array in the line return Search(nums[mid:], target), the new slice is nums=[30,39,55,67]. The index of 55 was 6 in the original slice but in the new slice, it is 2. That is why you are not getting the correct answer.
When you make a new slice from an existing slice, the index of the elements does not reflect the old slice. To make this up you need to add the current mid when you are selecting the right side of the slice for binary search.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论