H1dd3n
Explanation on Binary search
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
> endMost Liked
joey_the_snake
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.
adamu
Popular in Questions
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Supporting innovation across the BEAM ecosystem.
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #websockets
- #supervisor
- #elixirconf-us
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #metaprogramming
- #security
- #hex
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking for Elixir devs who love to ship. Start your free account.
Practical resources that improve the lives of professional developers.
Develop your skills with books, videos, and courses.
Enabling companies to succeed by building software people love.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"