Как этот рекурсивный код находит оригинальный индекс? - PullRequest
Новая
       5

Как этот рекурсивный код находит оригинальный индекс?

0 голосов
/ 15 января 2020

Я не понимаю, как он возвращает правильный ответ 

    def bsearch(array, target)

      return nil if array.length == 0

      midpoint = array.length / 2
      case target <=> array[midpoint]
      when -1
        bsearch(array.take(midpoint), target)
      when 0
        midpoint
      when 1
        index = bsearch(array.drop(midpoint + 1), target)
        (index.nil?) ? nil : (midpoint + 1) + index
      end
    end


    p bsearch([1, 3, 4, 5, 9], 5) # => 3

    p bsearch([1, 2, 3, 4, 5, 6], 6) # => 5

Каким-то образом он переходит с линии 10 (где он должен возвращать среднюю точку) на 13, где он каким-то образом снова получает исходный массив?!

Здесь была моя попытка, но она не удалась, возвращая среднюю точку последней рекурсивной версии массива 

    def bsearch(array, target)

      return nil if array.length == 0
      aim = array.length / 2

      return nil if array.length == 1 && array[0] != target

     case target <=> array[aim]
     when 0
        aim
     when -1
      bsearch(array[0...aim], target)
     when 1
      bsearch(array[aim..-1], target)
     end
    end

1 Ответ

1 голос
/ 15 января 2020

Основное различие между рассматриваемым кодом и вашей попыткой заключается в следующей строке: 

(index.nil?) ? nil : (midpoint + 1) + index

в последней ветке. И это на самом деле имеет значение.

Причина в том, что алгоритм «сжимает» массив при каждом промахе, поэтому массив, который вы просматриваете, становится меньше. Но вам все еще нужен целевой индекс в большем оригинальном массиве. Таким образом, каждый раз, когда вы берете «правый» подрешеток и отбрасываете «левый», вам нужно как-то настроить индекс. И это именно то, что делает эта линия.

...