## Test Driven Development of binary search

Binary search is one of the fundamental algorithms in computer science. In order to explore it, we’ll first build up a theoretical backbone, then use that to implement the algorithm properly and avoid those nasty off-by-one errors everyone’s been talking about.

### Finding a value in a sorted sequence

In its simplest form, binary search is used to quickly find a value in a sorted sequence (consider a sequence an ordinary array for now). We’ll call the sought value the target value for clarity. Binary search maintains a contiguous subsequence of the starting sequence where the target value is surely located. This is called the search space. The search space is initially the entire sequence. At each step, the algorithm compares the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space. By doing this repeatedly, it will eventually be left with a search space consisting of a single element, the target value.

### Complexity

Since each comparison binary search uses halves the search space, we can assert and easily prove that binary search will never use more than (in big-oh notation) O(log N) comparisons to find the target value.

#### Implementing the discrete algorithm

Create a file named binary_search.exs

``````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(numbers, key) do
binary_search(numbers, key, 0, tuple_size(numbers))
end

defp binary_search(numbers, _key, _low, _high) when tuple_size(numbers) < 1 do
:not_found
end

defp binary_search(_numbers, _key, low, high) when low > high do
:not_found
end

defp binary_search(numbers, key, low, high) when tuple_size(numbers) > 0 do
mid = div(low + high, 2)

if mid >= tuple_size(numbers) do
:not_found
else
item = elem(numbers, mid)

cond do
key < item -> binary_search(numbers, key, low, mid - 1)
key > item -> binary_search(numbers, key, mid + 1, high)
true -> {:ok, mid}
end
end
end
end
``````

#### Writing the test case

create a file binary_search_test.exs and write the test cases on it.

``````if !System.get_env("BINARY_SEARCH") do
end

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)

defmodule BinarySearchTest do
use ExUnit.Case

test "returns :not_found on empty tuple" do
assert BinarySearch.search({}, 2) == :not_found
end

# @tag :pending
test "returns :not_found when key is not in the tuple" do
assert BinarySearch.search({2, 4, 6}, 3) == :not_found
end

# @tag :pending
test "returns :not_found when key is too high" do
assert BinarySearch.search({2, 4, 6}, 9) == :not_found
end

# @tag :pending
test "finds key in a tuple with a single item" do
assert BinarySearch.search({3}, 3) == {:ok, 0}
end

# @tag :pending
test "finds key when it is the first element in tuple" do
assert BinarySearch.search({1, 2, 4, 5, 6}, 1) == {:ok, 0}
end

# @tag :pending
test "finds key when it is in the middle of the tuple" do
assert BinarySearch.search({1, 2, 4, 5, 6}, 4) == {:ok, 2}
end

# @tag :pending
test "finds key when it is the last element in tuple" do
assert BinarySearch.search({1, 2, 4, 5, 6}, 6) == {:ok, 4}
end

# @tag :pending
test "finds key in a tuple with an even number of elements" do
tuple = {1, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377}
assert BinarySearch.search(tuple, 21) == {:ok, 5}
assert BinarySearch.search(tuple, 34) == {:ok, 6}
end
end
``````

#### Running the test case

``````Run command elixir test binary_search_test.exs

#Output``````

#### Conclusion

If you’ve gotten this far without giving up, you should be ready to solve anything that can be solved with binary search. Try to keep a few things in mind:

• Design a predicate which can be efficiently evaluated and so that binary search can be applied
• Decide on what you’re looking for and code so that the search space always contains that (if it exists)
• If the search space consists only of integers, test your algorithm on a two-element set to be sure it doesn’t lock up
• Verify that the lower and upper bounds are not overly constrained: it’s usually better to relax them as long as it doesn’t break the predicate <