Метод рекурсивного индексирования / поиска в Ruby (с использованием среднего сравнения), возвращающий неверное значение индекса

Question

Самообучающийся Ruby на модуле рекурсии.

Я пишу метод, который будет принимать два аргумента: bsearch (array, target).Массив всегда будет отсортирован, и я хочу, чтобы этот метод возвращал индекс, по которому цель была найдена таким образом, с использованием рекурсии:

Сравните цель со средним элементом (отсортированного) массива.Если он больше среднего элемента, снова запустите метод во второй половине массива.Если он меньше среднего элемента, снова запустите метод с первой половиной массива.

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

def bsearch(arr, target)
    middle_index = arr.length / 2

    return middle_index if arr[middle_index] == target
    return nil if arr.length == 1

    if target > arr[middle_index]
        bsearch(arr[middle_index+1..-1], target)
    elsif target < arr[middle_index]
        bsearch(arr[0...middle_index], target)
    end
end

Когда я ввожу:

bsearch([1, 2, 3], 1) # => 0
bsearch([2, 3, 4, 5], 3) # => 1
bsearch([2, 4, 6, 8, 10], 6) # => 2

Все они выводятся правильно, но когда я запускаю:

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

Вместо этого они возвращают 0 и затем 1 соответственно.Я могу понять, почему они делают, поскольку 0 и 1 являются индексами цели в меньшей, более новой версии arr: [5,9] (5 с индексом 0), а затем [5,6] (6 с индексом1).

Как я могу получить доступ к правильному middle_index для этих двух случаев?

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

Answer 1

Каждый раз, когда вы возвращаетесь в правую половину поискового массива, ваш начальный индекс относительно исходного массива смещается на middle_index + 1.Итак, просто добавьте это смещение к результату!Вам нужно всего лишь изменить одну строку в вашем методе:

bsearch(arr[middle_index+1..-1], target)

становится

bsearch(arr[middle_index+1..-1], target) + middle_index + 1
#                                       ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑

Примечание!Ваш оригинальный метод был хвост-рекурсивным.Это не так, поскольку хвостовой вызов - +, а не bsearch.[Ruby не оптимизирует хвостовую рекурсию или хвостовые вызовы, поэтому это не имеет значения, но, например, Scala оптимизирует хвостовую рекурсию, а ECMAScript даже оптимизирует все хвостовые вызовы, поэтому в этих языках я теперь превратил совершенно безопасный метод с использованием O (1)память в метод, который использует O (log n) memory.]

Это потому, что мы должны сохранять наше состояние где-то , и когда мы программируем рекурсивно, мы обычно сохраняем наше состояние настек.(Этот стиль рекурсивного программирования типичен для чисто функциональных языков, которые не имеют изменяемых структур данных, и поэтому стек - это единственное место, где вы можете хранить состояние.)

В этом случаеЯ сохранил состояние в виде стека вызовов методов для +, которые выполняются после завершения фактического поиска.Однако в стеке хранятся две вещи: указатели инструкций и аргументы.

Итак, стандартный способ превратить нерекурсивный метод в хвостовой рекурсивный - это переместить значение, которое мынакапливать вызовы методов в аргументе и передавать его каждому последующему рекурсивному вызову.

Для этого необходимо изменить сигнатуру метода и добавить дополнительный параметр:

def bsearch(arr, target, offset)
#                      ↑↑↑↑↑↑↑↑
  middle_index = arr.length / 2

  return middle_index if arr[middle_index] == target
  return nil if arr.length == 1

  if target > arr[middle_index]
    bsearch(arr[middle_index+1..-1], target, offset)
    #                                      ↑↑↑↑↑↑↑↑
  elsif target < arr[middle_index]
    bsearch(arr[0...middle_index], target, offset)
    #                                    ↑↑↑↑↑↑↑↑
  end
end

bsearch([1, 3, 4, 5, 9], 5, nil)

В данный моментНа самом деле мы ничего не сделали, просто добавили новый параметр в определение метода, а затем, конечно, нам также нужно добавить аргумент для каждого вызова метода.Но мы пока ничего с этим не делаем.Нам нужно сделать что-нибудь с этим параметром.Мы делаем более или менее то же самое, что и раньше:

def bsearch(arr, target, offset)
  middle_index = arr.length / 2

  return offset + middle_index if arr[middle_index] == target
  #      ↑↑↑↑↑↑↑↑↑
  return nil if arr.length == 1

  if target > arr[middle_index]
    bsearch(arr[middle_index+1..-1], target, offset + middle_index + 1)
    #                                              ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
  elsif target < arr[middle_index]
    bsearch(arr[0...middle_index], target, offset)
  end
end

bsearch([1, 3, 4, 5, 9], 5, 0)
#                           ↑

Нам нужно убедиться, что мы «изменили» (то есть передали новое значение) аргумент, когда мы возвращаемся в правую половину поискамассив, нам нужно убедиться, что мы на самом деле добавляем накопленное значение, когда мы наконец нашли значение, и мы должны убедиться, что мы инициализируем его с правильным значением.

Это немного уродливо, хотя, поскольку мы изменили сигнатуру нашего метода, и теперь вызывающая сторона должна всегда указывать 0 в качестве последнего аргумента.Это плохой дизайн API.

Мы можем это исправить, сделав offset необязательным позиционным параметром со значением аргумента по умолчанию 0:

def bsearch(arr, target, offset=0)
#                              ↑↑

Тогда мы больше не будемнужно пройти 0 на сайте вызова.Но это все еще уродливо, так как оно все еще изменяет подпись, и, например, кто-то может случайно передать 42.По сути, теперь мы просочились в частную внутреннюю деталь реализации, а именно в значение нашего аккумулятора для того, чтобы сделать наш метод рекурсивным для внешней среды.Никого не волнует, реализовали ли мы наш метод, используя хвостовую рекурсию, или петлю, или отправив голубей-носителей в Китай и попросив детей-рабов в магазине пота найти номер вручную.(Ну, это было бы незаконно, аморально и ужасно, но это не должно быть частью сигнатуры нашего метода.)

Большинство языков, которые поддерживают надлежащие вызовы хвоста или правильную хвостовую рекурсию, также поддерживают вложенные или локальные подпрограммы,поэтому стандартным шаблоном для сокрытия деталей реализации, подобным этому, является наличие метода-обертки, который ничего не делает, кроме вызова вложенного метода, выполняющего реальную работу.Часто этот метод назван в честь внешнего метода с суффиксом, то есть в Haskell обычно используется вспомогательная функция для foo с именем foo' ("foo prime"), в Scala это fooRec.Иногда это просто называется go или doit.

Например, в Scala мы определяем наш метод следующим образом:

def bsearch[A : Ordering](arr: IndexedSeq[A])(target: A) = {
  def bsearchRec(arr: IndexedSeq[A], target: A, accumulator: Long = 0) = {
    ??? // the code
  }

  bsearchRec(arr, target)
}

или в ECMAScript следующим образом:

function bsearch(arr, target) {
  function bsearchRec(arr, target, accumulator = 0) {
    // the code
  }

  return bsearchRec(arr, target);
}

К сожалению, в Ruby нет таких подпрограмм.Нашими альтернативами являются закрытые методы и лямбды:

def bsearch(arr, target) bsearch_rec(arr, target) end

private def bsearch_rec(arr, target, offset=0)
  middle_index = arr.length / 2

  return offset + middle_index if arr[middle_index] == target
  return nil if arr.length == 1

  if target > arr[middle_index]
    bsearch_rec(arr[middle_index+1..-1], target, offset + middle_index + 1)
  elsif target < arr[middle_index]
    bsearch_rec(arr[0...middle_index], target, offset)
  end
end

bsearch([1, 3, 4, 5, 9], 5)

Или

def bsearch(arr, target)
  bsearch_rec = nil

  bsearch_rec = ->(arr, target, offset=0) {
    middle_index = arr.length / 2

    return offset + middle_index if arr[middle_index] == target
    return nil if arr.length == 1

    if target > arr[middle_index]
      bsearch_rec.(arr[middle_index+1..-1], target, offset + middle_index + 1)
    elsif target < arr[middle_index]
      bsearch_rec.(arr[0...middle_index], target, offset)
    end
  }

  bsearch_rec.(arr, target)
end

bsearch([1, 3, 4, 5, 9], 5)

Это создаст новую лямбду при каждом вызове, поэтому мы можем извлечь эту лямбду из метода влокальная переменная, но затем нам нужно превратить сам метод в блок, чтобы он мог закрывать эту переменную:

bsearch_rec = nil

bsearch_rec = ->(arr, target, offset=0) {
  middle_index = arr.length / 2

  return offset + middle_index if arr[middle_index] == target
  return nil if arr.length == 1

  if target > arr[middle_index]
    bsearch_rec.(arr[middle_index+1..-1], target, offset + middle_index + 1)
  elsif target < arr[middle_index]
    bsearch_rec.(arr[0...middle_index], target, offset)
  end
}

define_method(:bsearch) {|arr, target|
  bsearch_rec.(arr, target)
}

bsearch([1, 3, 4, 5, 9], 5)

Answer 2

Вы можете написать рекурсию следующим образом.

def bsearch(arr, target)
  return nil if target < arr.first || target > arr.last
  recurse(arr, target, 0, arr.size-1)
end

def recurse(arr, target, low, high)
  mid = (low+high)/2
  case target <=> arr[mid]
  when 0
    mid
  when -1
    recurse(arr, target, low, mid-1) unless low==mid
  when 1
    recurse(arr, target, mid+1, high) unless high==mid
  end
end

arr = [1, 2, 3, 5, 6]
bsearch(arr, 5) #=> 3 
bsearch arr, 1) #=> 0 
bsearch arr, 4) #=> nil 
bsearch arr, 0) #=> nil 

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

INDENT = 4

def indent
  @offset += INDENT
  puts
end

def undent
  @offset -= INDENT
  puts
end

def pu(str)
  puts ' '*@offset + str
end

def bsearch(arr, target)
  @offset = 0
  pu "passed to bsearch: arr=#{arr}, target=#{target}"
  puts
  return nil if target < arr.first || target > arr.last
  recurse(arr, target, 0, arr.size-1)
end

def recurse(arr, target, low, high)
  pu "passed to recurse: low=#{low}, high=#{high}"
  mid = (low+high)/2
  pu "mid=#{mid}"
  case target <=> arr[mid]
  when 0
    pu "target==arr[mid] so return mid=#{mid}"
    rv = mid
  when -1
    pu "target < arr[mid]"
    if low==mid
      rv = nil
      pu "low==mid so return nil"
    else
      pu "calling recurse(arr, target, #{low}, #{mid-1})"
      indent   
      rv = recurse(arr, target, low, mid-1)
      pu "recurse(arr, target, #{low}, #{mid-1}) returned #{rv}"
    end
  when 1
    pu "target > arr[mid]"
    if high==mid
      rv = nil
      pu "high==mid so return nil"
    else
      pu "calling recurse(arr, target, #{mid+1}, #{high})"
      indent   
      rv = recurse(arr, target, mid+1, high)
      pu "recurse(arr, target, #{mid+1}, #{high}) returned #{rv}"
    end
  end
  pu "returning #{rv.nil? ? "nil" : rv}"
  undent
  rv
end

bsearch [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13], 2 

печатает следующее.

passed to bsearch: arr=[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13]
                   target=2

passed to recurse: low=0, high=11
mid=5
target < arr[mid]
calling recurse(arr, target, 0, 4)

    passed to recurse: low=0, high=4
    mid=2
    target < arr[mid]
    calling recurse(arr, target, 0, 1)

        passed to recurse: low=0, high=1
        mid=0
        target > arr[mid]
        calling recurse(arr, target, 1, 1)

            passed to recurse: low=1, high=1
            mid=1
            target==arr[mid] so return mid=1
            returning 1

        recurse(arr, target, 1, 1) returned 1
        returning 1

    recurse(arr, target, 0, 1) returned 1
    returning 1

recurse(arr, target, 0, 4) returned 1
returning 1

Answer 3

Я бы предложил несколько настроек кода, чтобы он работал.Я вижу следующие основные проблемы:

• , когда цель находится в правой части, вам нужно отслеживать пропущенную часть массива, чтобы получить правильный индекс (добавлен idx в качестве аргумента);
• проверьте и верните также первый элемент правой части, бывает, что цель есть, но вы ее пропускаете;
• необходимо вернуть, когда индекс выходит за границы;

Итак, это код.Я оставил комментарии и отладочную печать :

def bsearch(arr, target, idx = 0)
  middle_index = arr.length / 2

  # debug print
  p "#{arr} - left: #{arr[0...middle_index]} - right: #{arr[middle_index + 1..-1]} - middle_element: #{arr[middle_index]} - middle_index: #{middle_index}"

  return middle_index + idx if arr[middle_index] == target

  # check also the right position, comment out the line below to see how the debug print changes
  return middle_index + idx + 1 if arr[middle_index + 1] == target

  # || !arr[middle_index] to exit if out of boundaries
  return nil if arr.length == 1 || !arr[middle_index] 

  if target > arr[middle_index]
    # add middle_index + 1 to idx to keep track of the dropped part of the array
    bsearch(arr[middle_index + 1..-1], target, idx += middle_index + 1 )
  else  # target < arr[middle_index]
    bsearch(arr[0...middle_index], target)
  end
end

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

---

Для оптимизированной версии, возможно, вы захотите изучить источник Array#index:)

Answer 4

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

Вы хотите отслеживать low_index и high_index (количество элементов) через рекурсию так, чтобыкаждый раз, когда вызывается метод, вы ищете значение между диапазоном индекса, а не подмножеством исходного списка.

# Array, Target, first index (0), number of elements in the array
def bsearch(arr, target, low, high)
    middle_index = (low + high) / 2

    if target > arr[middle_index]
        bsearch(arr, target, middle_index, high)
    elsif target < arr[middle_index]
        bsearch(arr, target, low, middle_index)
    elsif arr[middle_index] == target
      middle_index
    end
end


puts bsearch([1, 2, 3], 1, 0, 3)
#=> 0

puts bsearch([2, 3, 4, 5], 3, 0, 4)
#=> 1

puts bsearch([2, 4, 6, 8, 10], 6, 0, 5)
#=> 2

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

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

Это не учитывается, если элемент НЕ существует в спискеоднако это решение для пути рекурсии.