Test-Driven Development of Binary Search program in elixir

Binary search is one of the fundamental algorithms in computer science. In order to explore it, we’ll first build up a theoretical backbone, then use that to implement the algorithm properly and avoid those nasty off-by-one errors everyone’s been talking about.

Finding a value in a sorted sequence

In its simplest form, binary search is used to quickly find a value in a sorted sequence (consider a sequence an ordinary array for now). We’ll call the sought value the target value for clarity. Binary search maintains a contiguous subsequence of the starting sequence where the target value is surely located. This is called the search space. The search space is initially the entire sequence. At each step, the algorithm compares the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space. By doing this repeatedly, it will eventually be left with a search space consisting of a single element, the target value.

Complexity

Since each comparison binary search uses halves the search space, we can assert and easily prove that binary search will never use more than (in big-oh notation) O(log N) comparisons to find the target value.

Implementing the discrete algorithm

Create a file named binary_search.exs

defmodule BinarySearch do
  @doc """
    Searches for a key in the tuple using the binary search algorithm.
    It returns :not_found if the key is not in the tuple.
    Otherwise returns {:ok, index}.

    ## Examples

      iex> BinarySearch.search({}, 2)
      :not_found

      iex> BinarySearch.search({1, 3, 5}, 2)
      :not_found

      iex> BinarySearch.search({1, 3, 5}, 5)
      {:ok, 2}

  """

  @spec search(tuple, integer) :: {:ok, integer} | :not_found
  def search(numbers, key) do
    binary_search(numbers, key, 0, tuple_size(numbers))
  end

  defp binary_search(numbers, _key, _low, _high) when tuple_size(numbers) < 1 do
    :not_found
  end

  defp binary_search(_numbers, _key, low, high) when low > high do
    :not_found
  end

  defp binary_search(numbers, key, low, high) when tuple_size(numbers) > 0 do
    mid = div(low + high, 2)

    if mid >= tuple_size(numbers) do
      :not_found
    else
      item = elem(numbers, mid)

      cond do
        key < item -> binary_search(numbers, key, low, mid - 1)
        key > item -> binary_search(numbers, key, mid + 1, high)
        true -> {:ok, mid}
      end
    end
  end
end

Writing the test case

create a file binary_search_test.exs and write the test cases on it.

if !System.get_env("BINARY_SEARCH") do
  Code.load_file("binary_search.exs", __DIR__)
end

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)

defmodule BinarySearchTest do
  use ExUnit.Case

  test "returns :not_found on empty tuple" do
    assert BinarySearch.search({}, 2) == :not_found
  end

  # @tag :pending
  test "returns :not_found when key is not in the tuple" do
    assert BinarySearch.search({2, 4, 6}, 3) == :not_found
  end

  # @tag :pending
  test "returns :not_found when key is too high" do
    assert BinarySearch.search({2, 4, 6}, 9) == :not_found
  end

  # @tag :pending
  test "finds key in a tuple with a single item" do
    assert BinarySearch.search({3}, 3) == {:ok, 0}
  end

  # @tag :pending
  test "finds key when it is the first element in tuple" do
    assert BinarySearch.search({1, 2, 4, 5, 6}, 1) == {:ok, 0}
  end

  # @tag :pending
  test "finds key when it is in the middle of the tuple" do
    assert BinarySearch.search({1, 2, 4, 5, 6}, 4) == {:ok, 2}
  end

  # @tag :pending
  test "finds key when it is the last element in tuple" do
    assert BinarySearch.search({1, 2, 4, 5, 6}, 6) == {:ok, 4}
  end

  # @tag :pending
  test "finds key in a tuple with an even number of elements" do
    tuple = {1, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377}
    assert BinarySearch.search(tuple, 21) == {:ok, 5}
    assert BinarySearch.search(tuple, 34) == {:ok, 6}
  end
end

Running the test case

Run command elixir test binary_search_test.exs

#Output

Conclusion

If you’ve gotten this far without giving up, you should be ready to solve anything that can be solved with binary search. Try to keep a few things in mind:

  • Design a predicate which can be efficiently evaluated and so that binary search can be applied
  • Decide on what you’re looking for and code so that the search space always contains that (if it exists)
  • If the search space consists only of integers, test your algorithm on a two-element set to be sure it doesn’t lock up
  • Verify that the lower and upper bounds are not overly constrained: it’s usually better to relax them as long as it doesn’t break the predicate <

Leave a Reply

Your email address will not be published. Required fields are marked *