Расширение (Monkey Patching) бинарного поиска для класса Array и синтаксического сахара

Question

Я изучал несколько алгоритмов поиска, и моя последняя проблема сводится к бинарному поиску.Я посмотрел несколько видео на YouTube, чтобы понять концепцию, а затем попытался решить проблему, но продолжал получать ошибку бесконечного цикла.Я просмотрел переполнение стека и reddit, и куда бы меня ни привел Google, но я не могу найти решение, которое бы соответствовало моему методу кодирования.Кроме того, прошу прощения за термин «исправление обезьяны». Мне стало известно, что технический термин называется «расширение», так что вина моих инструкторов заключается в том, что он преподает нам его как «исправление обезьяны».

Вот мой код:

class Array
   def my_bsearch(target)

    return nil if self.empty?

    middle_idx = self.length/2

    left = self.take(middle_idx)
    right = self.drop(middle_idx + 1)

    return middle_idx if self[middle_idx] == target

    until self[middle_idx] == target || self.nil? == nil
      if self[middle_idx] < target
        right.my_bsearch(target)
      elsif self[middle_idx] > target
        left.my_bsearch(target)
      end
    end

  end
end

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

class Array
  def my_bsearch(target)
    return nil if size == 0
    mid = size/2

    case self[mid] <=> target
    when 0
      return mid
    when 1
      return self.take(mid).my_bsearch(target)
    else
      search_res = self.drop(mid+1).my_bsearch(target)
      search_res.nil? ? nil : mid + 1 + search_res
    end
  end
end

Я думаю, я понимаю случай /, несмотря на то, что я не пользуюсь им.Я пытался следить за этим с помощью отладчика, но я думаю, что зациклен на том, что происходит в разделе ELSE.Синтаксический сахар, хотя и делает это, очевидно, более кратким, чем моя логика, не является прямым / чистым для кого-либо из моего уровня грамотности в рубине.Так что да, мое невежество - большая часть проблемы, я думаю.

Есть ли кто-то немного более грамотный и терпеливый, способный помочь мне разбить это на что-то, что я могу понять немного лучше, чтобы я мог извлечь из этого уроки?

Answer 1

Во-первых, take и drop имеют достаточно схожие интерфейсы, поэтому вы не хотите, чтобы ваш + 1 был отброшен.Если вы это сделаете, он игнорирует один элемент в массиве.

Далее, self.nil? всегда будет false (и никогда nil) для экземпляров этого класса.Фактически, .nil? - это метод, позволяющий избежать необходимости сравнивать с nil с ==.

Вы хотите self.empty?.Кроме того, за исключением сеттеров, в Ruby сообщения отправляются на self по умолчанию.Другими словами, единственный полезный префикс self. - это когда сообщение оканчивается на = и работает как lvalue, как в self.instance_var = 'a constant', поскольку без self. токены instance_var = будут интерпретироваться.в качестве локальной переменной, а не установки переменной экземпляра.Это не тот случай, поэтому empty? будет достаточно, так же как и self.empty?

Answer 2

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

Итак, если у меня есть массив, и целью является middle_elementтогда он сообщит о middle_element_idx.Все в порядке.Что если цель меньше, чем middle_element?Он рекурсивно ищет в левой части исходного массива.Когда он находит его, он сообщает о left_side_idx.С этим проблем нет, потому что элементы в массиве последовательно считаются слева направо.Итак, он начинается с 0 и идет вверх.

Но что, если цель находится справа от среднего элемента?

Ну, поиск правой стороны очень прост.Относительно той же логики, что и у поиска.Сделано рекурсивно.И он вернет target_idx, если он найден с правой стороны - однако это idx цели, как он был найден в массиве справа!Итак, вам нужно взять возвращенный target_idx и добавить к нему 1 и оригинальный middle_element_idx.См. Ниже:

  def my_bsearch(target)

    return nil if self.empty?

    middle_idx = self.length/2
    left = self.take(middle_idx)
    right = self.drop(middle_idx + 1)

      if self[middle_idx] == target
        return middle_idx
      elsif self[middle_idx] > target
        return left.my_bsearch(target)
      else
        searched_right_side = 1 + right.my_bsearch(target)
        return nil if searched_right_side.nil? == true
        return searched_right_side + middle_idx
      end

  end
end

Обратите внимание, сколько еще строк это решение?Оператор космического корабля, используемый в сочетании с case / when и троичным методом, значительно сократит количество линий.

Основываясь на предложениях / отзывах Тима, я обновил его до:

  def my_bsearch(target)

    return nil if empty?

    middle_idx = self.length/2
    left = self.take(middle_idx)
    right = self.drop(middle_idx)

      if self[middle_idx] == target
        return middle_idx
      elsif self[middle_idx] > target
        return left.my_bsearch(target)
      else
        searched_right_side = right.my_bsearch(target)
        return nil if searched_right_side.nil?
        return searched_right_side + middle_idx
      end

  end
end