рекурсивный бинарный поиск в ruby - PullRequest
Новая
       14

рекурсивный бинарный поиск в ruby

0 голосов
/ 03 сентября 2018

Я изучал некоторые алгоритмы и не могу найти причину сбоя моего метода. если бы вы могли посмотреть на код и пролить свет на то, почему это происходит. Я был бы очень признателен.

Я пытаюсь написать метод, который бы выполнял бинарный поиск в массиве рекурсивно, и пока это весь мой код. 

 def recursive_binary_search(arr, target)
   max_index = arr.length - 1
   mid_index = max_index / 2

   if arr[mid_index] > target
     new_arr = arr[0..(mid_index - 1)]
     recursive_binary_search(new_arr, target)
   elsif arr[mid_index] < target
     new_arr = arr[(mid_index + 1)..max_index]
     recursive_binary_search(new_arr, target)
   else
     return mid_index
   end
 end

Я получаю ошибку: undefined method '>' for nil:NilClass

1 Ответ

0 голосов
/ 04 сентября 2018

Мне не удалось воспроизвести исключение, о котором сообщает OP (поскольку данные, которые привели к исключению, не были приведены в вопросе), но основная проблема заключается в том, что max_index вычисляется из arr, а arr постоянно уменьшается, возвращаемый методом индекс не будет иметь отношения к правильному индексу в исходном массиве arr.

Предположим, например, что arr = [1,2,3,4,5,6] и target = 6. В этом случае метод вернет 0 (а не 5) в качестве индекса целевого элемента. Это потому, что arr постепенно станет arr[3..6], arr[4..6], arr[5..6] и arr[6], после чего будет возвращен индекс 0.

Вот один способ, которым метод может быть написан с использованием оператора case. В этом методе предполагается, что target является элементом arr и (как требуется при бинарном поиске) элементы arr упорядочены, от наименьшего к наибольшему. 

def recursive_binary_search(arr, target, min_index=0, max_index=arr.size-1)
  mid_index = (min_index+max_index)/2
  case arr[mid_index] <=> target
  when  0  # arr[mid_index] == target
    mid_index
  when -1  # arr[mid_index] < target
    min_index = mid_index + 1
    recursive_binary_search(arr, target, min_index, max_index)
  when  1  # arr[mid_index] > target
    max_index = mid_index - 1
    recursive_binary_search(arr, target, min_index, max_index)
  end
end

arr = [1,2,3,4,5,6]

arr.each { |target| puts "#{target}: #{recursive_binary_search(arr, target)}" }
1: 0
2: 1
3: 2
4: 3
5: 4
6: 5
...