手动二进制搜索包装

是否有人会这么友好地向我解释我如何完成我的递归二进制搜索问题？递归方面令我困惑。如果可能的话，我会很乐意为你解释这是什么！我想我需要增加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)

来源

2017-01-08 Rob Matthews

一些稍微不同的需要：HTTP：// rosettacode。 org/wiki/Binary_search＃Ruby – JLB

half是问题的一部分。对于length为2,half将为0，您可以将数组“分割”为完整数组和空数组：递归永远不会结束。

您还需要保持一个索引，并添加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

来源

2017-01-08 18:16:36

Downvoter：请随时解释。 –

手动二进制搜索包装

回答

相关问题