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

a guest
Apr 19th, 2010
218
0
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.