为什么我的bsearch版本不能工作？

Question

我正在运行bsearch([1,2,3,4,5,6], 6)

这是我的bsearch版本：

def bsearch(arr, target)

    return nil if arr.size == 0

    half = arr.size / 2
    left = arr[0...half]
    right = arr[half...-1]

    case target <=> arr[half]
    when 1
      return half + bsearch(right, target)
    when 0
      return half
    when -1
      return bsearch(left, target)
    end
end

这是我被抛出的错误：

recursion.rb:224:in `+': nil can't be coerced into Fixnum (TypeError)
    from recursion.rb:224:in `bsearch'
    from recursion.rb:224:in `bsearch'
    from recursion.rb:249:in `<main>'

Answer 1

来自ruby docs

..从头到尾都要包括在内。它们是使用...排除结束值

您的代码排除了最后的数组元素。

left = arr[0...half]
right = arr[half...-1]

更改为对..而不是...使用范围运算符

left = arr[0..half]
right = arr[half..-1]

Answer 2

你应该添加一些调试代码，它可以帮助你节省很多时间，并找到根本原因。

def bsearch(arr, target)

    return nil if arr.size == 0

    half = arr.size / 2
    puts "half: #{half}"
    left = arr[0...half]
    puts "left:#{left}"
    puts "arr:#{arr}"
    right = arr[half...-1]
    puts "right:#{right}"
    ....
end

结果：

left:[1, 2, 3]
arr:[1, 2, 3, 4, 5, 6]
half:3
right:[4, 5]
left:[4]
arr:[4, 5]
half:1
right:[]
test.rb:16:in `+': nil can't be coerced into Fixnum (TypeError)
    from test.rb:16:in `bsearch'
    from test.rb:16:in `bsearch'
    from test.rb:24:in `<main>'

然后你会发现一些问题。

1. right :4，5 => it it be 4，5，6
2. arr = 4,5;half = 1；=> right= arr1...-1 = []

因此bsearch(right, target)将返回nil

你的代码应该是：

left = arr[0..half]
right = arr[half..-1]