Elixir binary search

Question

Elixir binary search

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:

Can you skip the conventions at all? Maybe with a match pattern?

+3

if-statement elixir binary-search

davidcunha Dec 11. '14 at 9:21

source to share

2 answers

You cannot do this with pattern matching. However, you can use cond

which is similar to Erlang if

:

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

+5

rightfold Dec 11. '14 at 9:47

source to share

Patrick oscity · Accepted Answer · 2014-12-11T10:28:36+0000

DISCLAIMER: Don't use this in production, it's slower than a simple linear search because linked lists don't allow random access at constant time. This message is only for the pattern matching aspect.

In theory, you can use the suggestions of the guard, but they can make things much worse if you overdo it. Assuming you start with the 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

Perhaps you want to extract if

into the protection proposal:

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 can also pull cond

in watchdogs , but this is 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

Elixir binary search

More articles: