Ruby实现二分搜索触发undefined method '>' for nil:NilClass报错
报错核心原因
问题出在循环内的中点索引计算逻辑存在运算优先级错误。
你代码里写的中点计算为:middle = first + last / 2
Ruby 中算术运算符的优先级里,/ 高于 +,因此这行代码实际的计算逻辑是 middle = first + (last / 2),完全不是二分查找需要的两个端点的中间位置。这种错误计算很容易产出超出数组有效索引范围的值,当通过这个错误索引取数组元素时,拿到的就是nil,后续拿nil和目标值做大小比较,就会触发你遇到的 undefined method '>' for nil:NilClass 报错。
举个实际运行的例子,用你给出的测试用例 nums = [1,2,3,4,5] 找目标值4:
- 第一次循环:
first=0, last=4,按错误逻辑计算的middle = 0 + 4/2 = 2,对应数组元素是3,比目标值小,因此把first更新为2+1=3 - 第二次循环:
first=3, last=4,再按错误逻辑计算的middle = 3 + 4/2 =5,而当前数组的有效索引范围是0-4,arr[5]返回nil,执行到elsif arr[middle] > n这行时就会直接抛出报错,和你遇到的现象完全匹配。
修正方案
- 给中点计算加上括号,保证先算两个端点的和再做除法:
middle = (first + last) / 2 - 删掉循环外冗余的
middle = arr.length / 2初始化代码——这行代码在进入循环后就会被覆盖,没有实际作用。
修正后可正常运行的完整代码:
def b_search(n, arr) first = 0 last = arr.length - 1 while first <= last middle = (first + last) / 2 if arr[middle] == n return true elsif arr[middle] > n last = middle - 1 else first = middle + 1 end end false end nums = [1, 2, 3, 4, 5] target = 4 if b_search(target, nums) puts "Target Found" else puts "Target Not Found" end
补充优化
如果后续处理的数组长度很大,更稳妥的中点计算写法可以调整为 middle = first + (last - first) / 2,计算结果和上面的写法完全一致,同时可以规避整数相加可能带来的溢出问题,更符合通用的二分查找实现规范。
内容的提问来源于stack exchange,提问作者beybladebarti
相关产品推荐
相关产品推荐

