如何在此Binary_search算法中控制nil

Question

我正在阅读Grokking算法书，并且正在递归地实现binary_search函数，因此，如果该项目在列表中，我的算法就可以工作。

关于零时如何控制的任何建议？

def recursive_binary_search(list, item)
  if list.length == 0
    return nil
  elsif list.length == 1
    print list
    if list.first == item
      return 0
    else
      return nil
    end
  else
    low = 0
    high = list.length - 1
    mid = (low + Float(high - low)/2).round()
    guess = list[mid]

    if guess == item
      return mid
    elsif guess < item
      return mid + 1 + recursive_binary_search(list[mid+1..-1], item)
    else
      return recursive_binary_search(list[0..mid-1], item)
    end
  end
end

my_list = [1, 3, 5, 7, 9]

puts recursive_binary_search(my_list, 100) # => nil

Answer 1

您接近。

首先，不需要计算中间索引的回转。只是说

mid = list.length / 2

Ruby中的整数除法会截断，因此结果始终是您想要的整数。

第二个递归调用是一个问题。它可以返回nil。因此，您需要保存返回值，并且如果返回值不是nil，则仅执行索引运算。

最后请注意，由于Ruby自然返回它计算的最后一个值，因此可以省略所有的return。这使函数作为表达式读取，更像Ruby。

def recursive_binary_search(list, item)
  if list.length == 0
    nil
  elsif list.length == 1
    if list.first == item
      0
    else
      nil
    end
  else
    mid = list.length / 2
    guess = list[mid]
    if guess == item
      mid
    elsif guess < item
      result = recursive_binary_search(list[mid+1..-1], item)
      if result.nil?
        nil
      else
        1 + result + mid
      end
    else
      recursive_binary_search(list[0..mid-1], item)
    end
  end
end

唯一需要return的情况是，当可能进行更多计算时，立即退出函数。

最后请注意，尽管这对于学习非常有用，但是在实际的实现中，您应避免在Ruby中进行尾递归，因为与某些其他语言不同，Ruby无法保证将其优化为循环。由于二进制搜索可以非常自然地实现而无需递归调用，因此您可以选择这样做。