35 lines
994 B
Elixir
35 lines
994 B
Elixir
|
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({}, _value), do: :not_found
|
||
|
|
def search(numbers, value), do: do_search(numbers, value, 0, tuple_size(numbers) - 1)
|
||
|
|
|
||
|
|
defp do_search(_numbers, _value, from, to) when from > to, do: :not_found
|
||
|
|
defp do_search(numbers, value, from, to) do
|
||
|
|
middle = div(from + to, 2)
|
||
|
|
element = elem(numbers, middle)
|
||
|
|
cond do
|
||
|
|
value == element -> {:ok, middle}
|
||
|
|
value < element -> do_search(numbers, value, from, middle - 1)
|
||
|
|
value > element -> do_search(numbers, value, middle + 1, to)
|
||
|
|
end
|
||
|
|
end
|
||
|
|
end
|