수동 바이너리 검색 마무리

Question

내 재귀적인 이진 검색 문제를 어떻게 끝내는 지 설명해 주실 분 있나요? 재귀적인 측면은 나를 혼란스럽게합니다. 나는 가능하다면 그 일을하는 것에 대한 설명을 좋아할 것이다 !!! 나는 if 또는 elsif 안에있는 '절반'값을 증가시켜야한다고 생각하지만, 어떻게 생겼는지는 모른다. 리팩토링하는 것보다는 현재 가지고있는 코드를 더 간단한 방법으로 추가하는 방법을 제안하십시오 ... 적어도 처음에는! 감사!

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이되고 전체 배열과 빈 배열에서 배열을 "분할"합니다. 재귀는 결코 끝나지 않을 것입니다.

당신은 또한 인덱스를 유지하고 2 차 배열을 고려할 때 그것에 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