Sha256: 0c71c889d3f40161fb5688308612bcaa686f25d0f55c991d17eca57dad40dfbe

Contents?: true

Size: 1003 Bytes

Versions: 69

Compression:

Stored size: 1003 Bytes

Contents

defmodule BinarySearch do
  @doc """
    Searches for a key in the list using the binary search algorithm.
    It returns :not_found if the key is not in the list.
    Otherwise returns the tuple {: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({}, _key), do: :not_found

  def search(numbers, key) do
    do_search(numbers, key, 0, tuple_size(numbers) - 1)
  end

  defp do_search(_numbers, _key, low, high) when high < low, do: :not_found

  defp do_search(numbers, key, low, high) do
    middle = div(low + high, 2)
    middle_value = elem(numbers, middle)

    cond do
      key < middle_value -> do_search(numbers, key, low, middle - 1)
      key > middle_value -> do_search(numbers, key, middle + 1, high)
      true -> {:ok, middle}
    end
  end
end

Version data entries

69 entries across 69 versions & 1 rubygems

Version Path
trackler-2.2.1.180 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.179 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.178 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.177 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.176 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.175 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.174 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.173 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.172 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.171 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.170 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.169 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.167 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.166 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.165 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.164 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.163 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.162 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.161 tracks/elixir/exercises/binary-search/example.exs
trackler-2.2.1.160 tracks/elixir/exercises/binary-search/example.exs