Elixir 二分查找

Question

我在Elixir中构建了一个二分查找，但最终使用了3个if语句：

if actual == guessed_number, do:

if actual > guessed_number do:

if actual < guessed_number do:

完全不使用条件语句是可能的吗？也许可以使用模式匹配？

- davidcunha

Answer 1

免责声明：本文不适用于生产环境，因为链表不支持常数时间内的随机访问，因此比简单的线性搜索要慢。本文只是关于模式匹配方面的内容。

---

理论上你可以使用守卫条款，但如果过度使用会使情况变得更糟。假设你从像这样的实现开始：

defmodule MyEnum do
  def binsearch(collection, key) do
    binsearch(collection, key, 1, length(collection))
  end

  defp binsearch(collection, key, lo, hi) do
    if hi < lo do
      -1
    else
      mid = div(lo + hi, 2)
      item = Enum.at(collection, mid)
      cond do
        key < item -> binsearch(collection, key, lo, mid-1)
        key > item -> binsearch(collection, key, mid+1, hi)
        true       -> mid
      end
    end
  end
end

也许你想将 if 提取为一个守卫条款：

defmodule MyEnum do
  def binsearch(collection, key) do
    binsearch(collection, key, 1, length(collection))
  end

  defp binsearch(_collection, _key, lo, hi) when hi < lo do
    -1
  end

  defp binsearch(collection, key, lo, hi) do
    mid = div(lo + hi, 2)
    item = Enum.at(collection, mid)
    cond do
      key < item -> binsearch(collection, key, lo, mid-1)
      key > item -> binsearch(collection, key, mid+1, hi)
      true       -> mid
    end
  end
end

现在你也可以将cond移到守卫子句中，但这并不是真正的改进：

defmodule MyEnum do
  def binsearch(collection, key) do
    binsearch(collection, key, 1, length(collection))
  end

  defp binsearch(_collection, _key, low, hi) when hi < low do
    -1
  end

  defp binsearch(collection, key, low, hi) do
    mid = div(low + hi, 2)
    item = Enum.at(collection, mid)
    binsearch(collection, key, item, low, mid, hi)
  end

  defp binsearch(collection, key, item, low, mid, _hi) when key < item do
    binsearch(collection, key, low, mid-1)
  end

  defp binsearch(collection, key, item, _low, mid, hi) when key > item do
    binsearch(collection, key, mid+1, hi)
  end

  defp binsearch(_collection, _key, _item, _low, mid, _hi) do
    mid
  end
end

- Patrick Oscity

---

感谢您详细的回复。是的，将条件语句转换为守卫语句可能会变得有些复杂。 - davidcunha

如果集合具有 O(1) 的查找，则二分搜索才是高效的。Enum.at 的运行时间为线性的，因此这种二分搜索比简单的线性搜索要慢。 - John La Rooy

谢谢，非常好的观点。当我写下这个答案时，我刚开始接触Elixir，可能因为关注模式匹配而忽略了这一点。 - Patrick Oscity

我建议在顶部添加有关时间复杂度的注释，这样其他人就不会感到困惑。据我所知，在一般的链表上不可能进行 O(log(n) 二分查找。 - Vitalii Elenhaupt

Answer 2

使用模式匹配无法完成这个任务。但是，你可以使用类似于 Erlang 的 if 的 cond：

cond do
    actual == guessed_number ->
        ...
    actual > guessed_number ->
        ...
    actual < guessed_number ->
        ...
end

- user1804599

---

我也尝试了这种方法，我认为它是有效的，但不是我想要的。无论如何，还是谢谢。 - davidcunha