BinSearch

from __future__ import division
import unittest

##  Binary Search ##
####################

# Problem: a function that accepts a SORTED list and an item x and returns first index of item >= x.
# return len() if all items are smaller than x or if list is empty
# note that x may appear several times in the list
def BinSearchStupid(alist, x):
    for i, y in enumerate(alist):
        if y >= x:
            return i
    return len(alist)



class TestBinSearch(unittest.TestCase):

  def test_All(self):
      funcs = [BinSearchStupid,
               ]
      for f in funcs:
          self.do_func(f)

   def do_func(self, func):
      a = [1,1,1,1,1,1]
      i = func(a, 1)
      self.assertEqual(0, i)
      i = func(a, 2)
      self.assertEqual(6, i)
      a = [1,2,3,4,5]
      i = func(a, 3)
      self.assertEqual(2, i)
      a = [1,2,3,4,5,6]
      i = func(a, 3)
      self.assertEqual(2, i)
      a = [1,2,3,3,3,4,5,6]
      i = func(a, 3)
      self.assertEqual(2, i)
      a = [1,2,4,4,4,4,5,6]
      i = func(a, 3)
      self.assertEqual(2, i)
      a = []
      i = func(a, 3)
      self.assertEqual(0, i)
      a = [3]
      i = func(a, 3)
      self.assertEqual(0, i)
      i = func(a, 4)
      self.assertEqual(1, i)
      a = [3,3]
      i = func(a, 3)
      self.assertEqual(0, i)
      i = func(a, 4)
      self.assertEqual(2, i)