如果目标是数组中的第一个或最后一个元素，则二进制搜索递归函数不起作用

Question

我在 Ruby 中研究这个递归函数已经有一段时间了。有一个问题，我似乎无法自行解决。

def bsearch(array, target)
    pos = (array.length - 1) / 2
    return pos if array[pos] == target
    if array[pos] < target
        pos += bsearch(array[pos..-1], target)
    else
        pos -= bsearch(array[0..pos], target)
    end
end

只要目标不是数组中的第一个或最后一个元素，代码似乎就可以工作。我找不到这个问题的解决方案。

Answer 1

行

pos -= bsearch(array[0..pos], target)

其实应该是

bsearch(array[0..pos], target)

你想一想，如果你的数组长度为200，而你要查找的项目在数组前半部分的位置5，它也在整个数组的位置5。

如果目标是数组中的第一个或最后一个元素，则二进制搜索递归函数不起作用

Binary search recursive function not working if target is either the first, or last element in the array

ruby

binary-tree