手动二进制搜索总结

Question

谁能好心向我解释一下我是如何完成我的递归二分搜索问题的？递归方面让我感到困惑。如果可能的话，我很想解释一下它在做什么！！！我想我需要增加 if 或 elsif 中的 'half' 值，但我不知道它会是什么样子。请建议添加到我当前拥有的代码中的方法，而不是重构为更简单的代码……至少在一开始！谢谢！

def binary_search(letter, array)
  half = (array.length - 1)/2
  if letter == array[half]
    return half
  end
  if letter > array[half] && letter <= array[-1]
    array = array[half...array.length]
    binary_search(letter, array)
  elsif letter < array[half] && letter >= array[0]
    array = array[0...half]
    binary_search(letter, array)
  else
    nil
  end
end

arr = [:A, :B, :C, :D, :E, :F, :G]
p binary_search(:C, arr)

Answer 1

half 是问题的一部分。如果 length 为 2，half 将是 0，并且您将 "split" 您的数组是一个完整数组和一个空数组：递归永远不会结束。

您还需要保留一个索引，并在考虑第二个数组时向其添加half :

def binary_search(letter, array, i=0)
  puts "Been here for #{array} with #{i}"
  half = array.length / 2
  if letter == array[half]
    return i + half
  end
  if letter > array[half] && letter <= array[-1]
    binary_search(letter, array.drop(half), i + half)
  elsif letter < array[half] && letter >= array[0]
    binary_search(letter, array.take(half), i)
  else
    nil
  end
end

arr = [:A, :B, :C, :D, :E, :F, :G]
p binary_search(:C, arr)
p binary_search(:G, arr)

输出

Been here for [:A, :B, :C, :D, :E, :F, :G] with 0
Been here for [:A, :B, :C] with 0
Been here for [:B, :C] with 1
2
Been here for [:A, :B, :C, :D, :E, :F, :G] with 0
Been here for [:D, :E, :F, :G] with 3
Been here for [:F, :G] with 5
6

手动二进制搜索总结

manual binary search wrap up

ruby

recursion

if-statement

binary-search