Mercurial > hg > config

comparison python/example/binarysearch.py @ 566:e3341b7ce4ef

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
binarysearch
author Jeff Hammel <jhammel@mozilla.com>
date Mon, 30 Dec 2013 12:22:13 -0800
parents
children
comparison
equal deleted inserted replaced
565:7b70e5c0d410 566:e3341b7ce4ef
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()