Guest User

My binary search entry, 40 minutes, all tests pass so far.

a guest
Apr 19th, 2010
181
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python
  2.  
  3. """
  4. See http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
  5. """
  6.  
  7. import math
  8.  
  9. def bsearch(search_value, input_array):
  10.     """
  11.    Assume array is sorted, min at [0] and max at [-1]
  12.    """
  13.  
  14.     # Ending conditions
  15.     if len(input_array) <= 0:
  16.         return False
  17.     if search_value < input_array[0]:
  18.         return False
  19.     if search_value > input_array[-1]:
  20.         return False
  21.  
  22.     split_index = int(math.floor(len(input_array) / 2))
  23.  
  24.     if input_array[split_index] == search_value:
  25.         return True
  26.  
  27.     if search_value > input_array[split_index]:
  28.         return bsearch(search_value, input_array[split_index+1:])
  29.     else:
  30.         return bsearch(search_value, input_array[0:split_index])
  31.  
  32. Test code:
  33. #!/usr/bin/env python
  34.  
  35. import unittest
  36. import logging
  37.  
  38. from pfh_bsearch import bsearch
  39.  
  40. class BsearchTester(unittest.TestCase):
  41.     def setUp(self):
  42.         logging.basicConfig(level=logging.INFO, format='%(asctime)s %(levelname)s [%(funcName)s] %(message)s')
  43.  
  44.     def test_404(self):
  45.         a = [1,2,3]
  46.         b = 4
  47.         rc = bsearch(b, a)
  48.         self.failUnlessEqual(rc, False)
  49.  
  50.         b = 0
  51.         rc = bsearch(b, a)
  52.         self.failUnlessEqual(rc, False)
  53.  
  54.         a = [1,2,3,4]
  55.         rc = bsearch(b, a)
  56.         self.failUnlessEqual(rc, False)
  57.  
  58.     def test_find(self):
  59.         a = [0,1,3,5]
  60.         b = 1
  61.         rc = bsearch(b, a)
  62.         self.failUnlessEqual(rc, True)
  63.         b = 0
  64.         rc = bsearch(b, a)
  65.         self.failUnlessEqual(rc, True)
  66.         b = 3
  67.         rc = bsearch(b, a)
  68.         self.failUnlessEqual(rc, True)
  69.         b = 5
  70.         rc = bsearch(b, a)
  71.         self.failUnlessEqual(rc, True)
  72.  
  73.     def test_corner_cases(self):
  74.         a = []
  75.         b = 42
  76.         rc = bsearch(b, a)
  77.         self.failUnlessEqual(rc, False)
  78.  
  79.         a = [1]
  80.         rc = bsearch(b, a)
  81.         self.failUnlessEqual(rc, False)
  82.  
  83. suite = unittest.TestLoader().loadTestsFromTestCase(BsearchTester)
  84. unittest.TextTestRunner(verbosity=2).run(suite)
RAW Paste Data