Explanation on Binary search

Questions / Help
1

I have some code that does Binary search but i’m having hard time understanding the logic behind it.
Could some one explain what each function does especially the last one where’s some logic going on.

  > @spec search(tuple, integer) :: {:ok, integer} | :not_found
>   def search({}, _key), do: :not_found
>   def search(numbers, key), do: search(numbers, key, 0, tuple_size(numbers) - 1)   
> 
>   def search(numbers, key, 0, 1) when elem(numbers, 0) == key, do: {:ok, 0}
>   
>   def search(numbers, key, min, max) when div(max - min, 2) == 0 and elem(numbers, max) == key, do: {:ok, max}
> 
>   def search(numbers, key, min, max) do
>     middle = div(max - min, 2) + min
>     value = elem(numbers, middle)
>     
>     cond do
>       value == key -> {:ok, middle}
>       middle == max or middle == min -> :not_found
>       value < key -> search(numbers, key, middle, max)
>       value > key -> search(numbers, key, min, middle)
>     end
>   end
2

In binary search you are looking for a value in a sorted array (or tuple in Elixir case). The gist of the algorithm:

  • Set the min and max indices to confine your search area. At the beginning min = 0 and max = length(tuple_or_array) - 1.

  • Check the value corresponding to the index that is the midpoint between your min and max indices. If it is the value you are looking for, stop. If it’s not then keep going.

  • If the value you’re looking for is greater than the one at the midpoint then you know it must be at an index greater than the midpoint, because the list is sorted. So your new min is the midpoint and you search again within this new range.

  • If the value you’re looking for is less than the one at the midpoint then you know it must be at an index less than the midpoint, because the list is sorted. So your new max is the midpoint and you search again within this new range.

  • If your range is confined to just the first index or just the last index and you haven’t found the value then you’ve exhausted the entire array/tuple and what you’re searching for doesn’t exist.

2 Likes
3

Cross-post from Explain this Elixir binary search implementation - Stack Overflow

1 Like