binary_search.py

#!/usr/local/bin/python3.6
# -*- coding: utf-8 -*-
from hypothesis import given, example
import hypothesis.strategies as st

def linear_search(key, l):
  """Given a search key and a list of tuples (key, value), return
  the first item that matches the key, or None if none match.

  Example:
    linear_search(1, [(0, "a"), (1, "b"), (6, "c")]) == "b"
    linear_search(5, [(0, "a"), (1, "b"), (6, "c")]) == None
  """
  for k, item in l:
    if k == key:
      return item
  else:
    return None

def binary_search(key, l):
  """Given a search key and a list of tuples (key, value) sorted by key, return
  the first item that matches the key, or None if none match.  Uses binary search.

  You can assume keys are ints.

  Example:
    binary_search(1, [(0, "a"), (1, "b"), (6, "c")]) == "b"
    binary_search(5, [(0, "a"), (1, "b"), (6, "c")]) == None
  """
  raise NotImplementedError("Binary search not implemented.")

@given(k=st.integers(), l=st.lists(st.tuples(st.integers(), st.text())).map(sorted))
def test_reference_implementation(k, l):
  """Test that binary search gives the same result as linear search on a sorted list."""
  linear = linear_search(k, l)
  binary = binary_search(k, l)
  assert linear == binary, "{} != {}".format(repr(linear), repr(binary))


@given(k=st.integers(), l=st.lists(st.tuples(st.integers(), st.text()), unique_by=(lambda kv:kv[0])).map(sorted))
def test_reference_implementation_uniq(k, l):
  """Test that binary search gives the same result as linear search on a sorted list."""
  linear = linear_search(k, l)
  binary = binary_search(k, l)
  assert linear == binary, "{} != {}".format(repr(linear), repr(binary))


if __name__ == '__main__':
  print("Uniq keys only:")
  test_reference_implementation_uniq()
  print("Allow repeated keys:")
  test_reference_implementation()

$ python3 binary_search.py
Uniq keys only:
Falsifying example: test_reference_implementation_uniq(k=0, l=[])
Traceback (most recent call last):
  File "binary_search.py", line 65, in <module>
    test_reference_implementation_uniq()
  File "binary_search.py", line 56, in test_reference_implementation_uniq
    def test_reference_implementation_uniq(k, l):
  File "/usr/local/lib/python3.6/site-packages/hypothesis/core.py", line 648, in wrapped_test
    state.run()
  File "/usr/local/lib/python3.6/site-packages/hypothesis/core.py", line 542, in run
    print_example=True, is_final=True
  File "/usr/local/lib/python3.6/site-packages/hypothesis/executors.py", line 58, in default_new_style_executor
    return function(data)
  File "/usr/local/lib/python3.6/site-packages/hypothesis/core.py", line 111, in run
    return test(*args, **kwargs)
  File "binary_search.py", line 59, in test_reference_implementation_uniq
    binary = binary_search(k, l)
  File "binary_search.py", line 30, in binary_search
    raise NotImplementedError("Binary search not implemented.")
NotImplementedError: Binary search not implemented.

It shows you that the smallest counterexample is test_reference_implementation_uniq(k=0, l=[]) (which is super-simple, since we haven't implemented anything yet).