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()
