Binary search tested with hypothesis

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"), (5, "c")]) == "b"
    linear_search(5, [(0, "a"), (1, "b"), (5, "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"), (5, "c")]) == "b"
    binary_search(5, [(0, "a"), (1, "b"), (5, "c")]) == None
  """

  if l is None or l == [] or type(l) is not list:
      return None

  mid = len(l) // 2

  k, v = l[mid]
  if k == key:
    return v
  elif k > key:
    return binary_search(key, l[0:mid])
  elif k < key:
    return binary_search(key, l[mid + 1:])

  return None

@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 (k,v):k)).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()