Elixir binary search

Question

I built a binary search in Elixir but I ended up using 3 if clauses:

if actual == guessed_number, do:

if actual > guessed_number do:

if actual < guessed_number do:

Is it possible to not use conditionals at all? Maybe with Pattern Matching?

Answer 1

DISCLAIMER: do not use this in production, this is slower than a simple linear search because linked lists do not allow for random access in constant time. This post is merely about the pattern matching aspect.

---

Theoretically you can use guard clauses, but they can make things much worse if you overdo it. Assuming you start with an implementation like this:

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

Maybe you want to extract the if into a guard clause:

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

Now you could also pull the cond out into guard clauses but it's not really an improvement:

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

Answer 2

You cannot do this with pattern matching. However, you can use cond which is like Erlang's if:

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