|
566
|
1 #!/usr/bin/env python
|
|
|
2
|
|
|
3 def find_index(ordered_array, to_find):
|
|
|
4 """
|
|
|
5 Return index of ``to_find`` via binary search.
|
|
|
6 Returns None if not in ``ordered_array``
|
|
|
7
|
|
|
8 ordered_array -- array of ordered values
|
|
|
9 to
|
|
|
10 """
|
|
|
11 if not ordered_array:
|
|
|
12 return
|
|
|
13 minimum = 0
|
|
|
14 maximum = len(ordered_array)-1
|
|
|
15 while True:
|
|
|
16 middle = (minimum + maximum)/2
|
|
|
17 value = ordered_array[middle]
|
|
|
18 if value == to_find:
|
|
|
19 return middle
|
|
|
20 if maximum == minimum:
|
|
|
21 return
|
|
|
22 if value < to_find:
|
|
|
23 minimum = middle+1
|
|
|
24 continue
|
|
|
25 if value > to_find:
|
|
|
26 maximum = middle
|
|
|
27 continue
|
|
|
28
|
|
|
29 if __name__ == '__main__':
|
|
|
30 import unittest
|
|
|
31
|
|
|
32 class TestFindIndex(unittest.TestCase):
|
|
|
33 values = [1,2,4,8,16,17]
|
|
|
34 def test_spotcheck(self):
|
|
|
35 for index, value in enumerate(self.values):
|
|
|
36 self.assertEqual(find_index(self.values, value), index)
|
|
|
37
|
|
|
38 unittest.main()
|
