Skip to content

Instantly share code, notes, and snippets.

@aokolish
Last active June 16, 2016 23:34
Show Gist options
  • Save aokolish/7739036 to your computer and use it in GitHub Desktop.
Save aokolish/7739036 to your computer and use it in GitHub Desktop.
binary search. `elixir search.exs` to run this. assuming you have elixir (`brew install elixir`)
defmodule Search do
def chop(_val, []), do: -1
def chop(val, [head|tail]) when tail == [] do
if val == head, do: 0, else: -1
end
def chop(val, list) do
chop(val, 0, length(list) - 1, list)
end
def chop(val, left, right, list) when right - left == 1 do
cond do
Enum.at(list, left) == val -> left
Enum.at(list, right) == val -> right
true -> -1
end
end
def chop(val, left, right, list) do
middle = round((right - left)/2)
mid_val = Enum.at(list, middle)
if (mid_val > val),
do: chop(val, left, middle, list),
else: chop(val, middle, right, list)
end
end
Code.require_file "../search.exs", __FILE__
ExUnit.start
defmodule TestChop do
use ExUnit.Case
test "chop on small or empty lists" do
assert Search.chop(1, []) == -1
assert Search.chop(1, [3]) == -1
assert Search.chop(1, [1]) == 0
end
test "chop on normal lists" do
assert Search.chop(1, [1, 3]) == 0
assert Search.chop(1, [1, 3, 5]) == 0
assert Search.chop(3, [1, 3, 5]) == 1
assert Search.chop(5, [1, 3, 5]) == 2
assert Search.chop(2, [1, 3, 5]) == -1
assert Search.chop(6, [1, 3, 5]) == -1
end
test "more cases" do
assert Search.chop(1, [1, 3, 5, 7]) == 0
assert Search.chop(5, [1, 3, 5, 7]) == 2
assert Search.chop(3, [1, 3, 5, 7]) == 1
assert Search.chop(7, [1, 3, 5, 7]) == 3
assert Search.chop(0, [1, 3, 5, 7]) == -1
assert Search.chop(2, [1, 3, 5, 7]) == -1
assert Search.chop(4, [1, 3, 5, 7]) == -1
assert Search.chop(6, [1, 3, 5, 7]) == -1
assert Search.chop(8, [1, 3, 5, 7]) == -1
end
end
@johnlr
Copy link

johnlr commented Jun 16, 2016

The catch here is that Enum.at works in linear time, so this has worse performance than just doing a linear search

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment