annotate python/example/binarysearch.py @ 838:3cda483d71b2

add .tox to hgignore
author Jeff Hammel <k0scist@gmail.com>
date Fri, 31 Mar 2017 16:30:52 -0700
parents e3341b7ce4ef
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
566
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
1 #!/usr/bin/env python
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
2
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
3 def find_index(ordered_array, to_find):
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
4 """
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
5 Return index of ``to_find`` via binary search.
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
6 Returns None if not in ``ordered_array``
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
7
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
8 ordered_array -- array of ordered values
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
9 to
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
10 """
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
11 if not ordered_array:
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
12 return
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
13 minimum = 0
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
14 maximum = len(ordered_array)-1
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
15 while True:
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
16 middle = (minimum + maximum)/2
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
17 value = ordered_array[middle]
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
18 if value == to_find:
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
19 return middle
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
20 if maximum == minimum:
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
21 return
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
22 if value < to_find:
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
23 minimum = middle+1
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
24 continue
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
25 if value > to_find:
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
26 maximum = middle
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
27 continue
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
28
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
29 if __name__ == '__main__':
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
30 import unittest
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
31
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
32 class TestFindIndex(unittest.TestCase):
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
33 values = [1,2,4,8,16,17]
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
34 def test_spotcheck(self):
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
35 for index, value in enumerate(self.values):
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
36 self.assertEqual(find_index(self.values, value), index)
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
37
e3341b7ce4ef binarysearch
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
38 unittest.main()