扩展(Monkey Patching)数组类和语法糖的二进制搜索

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

我想我理解case/when，尽管我不习惯使用它。我尝试过使用debugger来跟踪它，但我想我被ELSE部分中发生的事情挂住了。语法糖，虽然使这明显比我的逻辑更简洁，但对于我的ruby水平的人来说并不是直接/干净的。所以，是的，我想我的无知是最大的问题。

有没有人更有文化，更有耐心，能帮我把它分解成一些我能更好理解的东西，这样我就能从中学到东西？

Answer 1

首先，take和drop的接口非常相似，你实际上并不想让你的+ 1丢弃。如果您这样做，它将忽略数组中的一个元素。

接下来，对于该类的实例，self.nil?将始终为false (而不是nil)。事实上，.nil?是一种方法，它可以避免与使用==的nil进行比较。

你想要self.empty?。此外，在Ruby中，除了setter之外，默认情况下消息都会发送到self。换句话说，只有当消息以=结尾并作为左值操作时，self.才是有用的前缀，这是因为如果没有self.，令牌instance_var =将被解释为局部变量，而不是实例变量设置。这里不是这种情况，所以empty?和self.empty?一样就足够了

Answer 2

所以我想明白了，我决定回复我自己的帖子，希望能帮助别人解决这个问题。

因此，如果我有一个数组，并且目标是middle_element，那么它将报告middle_element_idx。这很好。如果目标小于middle_element怎么办？它递归地搜索原始Array的左侧。当它找到它时，它会报告left_side_idx。这是没有问题的，因为数组中的元素是从左到右顺序计数的。因此，它从0开始，然后上升。

但是，如果目标在中间元素的右侧呢？

好吧，寻找正确的一面是很容易的。与向左搜索的逻辑相对相同。递归地完成。如果在右侧找到，它将返回一个target_idx --然而，这是目标的idx，因为它是在右侧数组中找到的！因此，您需要将返回的target_idx与原始middle_element_idx相加1。如下所示：

  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和三元方法结合使用将显著减少线数。

根据Tim的建议/反馈，我将其更新为：

  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