H1dd3n
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
Where Next?
Trending in Questions
Other Trending Topics
Latest on Elixir Forum
Sponsor Spotlight
We build reliable cloud platforms for business-critical systems.
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #library
- #deployment
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #ai
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #blog-post
- #elixirconf-us
- #elixir-ls
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #elixirconf-eu
- #api
- #forms
- #security
- #performance
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.
Elixir, Erlang & BEAM conferences from Code Sync - join us in 2026!
Practical resources that improve the lives of professional developers.
Producing high quality Elixir screencasts since 2017.
The deployment platform built for Elixir: PaaS ease, VPS control.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
Showing Posts 1 to 2- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
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
Cross-post from https://stackoverflow.com/questions/72170033/explain-this-elixir-binary-search-implementation