Binary Search in Elixir

Disclaimer: Implementing binary search in Elixir may not be as performant as in languages with native array support. Elixir's lists are linked lists, which have O(n) time complexity for accessing elements by index. This impacts the efficiency of binary search, which relies on quick random access. In contrast, languages like C or Rust have O(1) array access, making binary search more efficient. However, Elixir's choice of linked lists aligns with its design goals of immutability, concurrency, and fault tolerance. Different languages have different trade-offs and are designed for different purposes.

Binary Search in Elixir

Let's implement a quick and dirty version of binary search, and we'll improve upon it after identifying the base case and the recursive case. We have to use recursion because it's the only way to iterate through a list in Elixir. Elixir also has for loops but they are more like the list comprehensions you find in Python.

defmodule Binary do
  def search(list, target) do
    search(list, target, 0, length(list) - 1)
  end

  def search(list, target, min, max) do
    if min <= max do
      # div performs integer division
      mid = div(max + min, 2)
      guess = Enum.at(list, mid)

      cond do
        # base case 1, lucky guess
        target == guess -> mid

        # recursive case
        guess > target -> search(list, target, min, (mid - 1))
        guess < target -> search(list, target, (mid + 1), max)

        # base case 2, target not found
        true -> -1
      end
    end
  end
end

Do you notice a problem with the code above? It doesn't return -1 if the target isn't found. We're also missing a pattern match to handle the case when the list is empty. Let's improve our algorithm by using a more idiomatic Elixir. Let's start by replacing the cond expression with a case expression

defmodule Binary do
  def search(list, target) do
    search(list, target, 0, length(list) - 1)
  end

  def search([], _target, _min, _max), do: -1

  def search(list, target, min, max) when min <= max do
    mid = div(max + min, 2)

    case Enum.at(list, mid) do
      ^target -> mid
      guess when guess > target -> search(list, target, min, mid - 1)
      _ -> search(list, target, mid + 1, max)
    end
  end

  def search(_list, _target, _min, _max), do: -1
end

Binary.search([1, 2, 3, 4, 5], 3) # => 2
Binary.search([1, 2, 3, 4, 5], 6) # => -1

Notice how we added a guard when min <= max to search/4 to ensure the search continues only when the minimum index is less than or equal to the maximum index. The pin operator ^ also helps us get rid of the if inside our recursive case.