Mercurial > hg > config

annotate python/example/binarysearch.py @ 694:ebca6d85213a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
File "/usr/lib/python3/dist-packages/IPython/config/__init__.py", line 16, in <module> from .application import * File "/usr/lib/python3/dist-packages/IPython/config/application.py", line 31, in <module> from IPython.config.configurable import SingletonConfigurable File "/usr/lib/python3/dist-packages/IPython/config/configurable.py", line 33, in <module> from IPython.utils.text import indent, wrap_paragraphs File "/usr/lib/python3/dist-packages/IPython/utils/text.py", line 28, in <module> from IPython.external.path import path File "/usr/lib/python3/dist-packages/IPython/external/path/__init__.py", line 2, in <module> from path import * File "/home/jhammel/python/path.py", line 25 print root(path) ^
author Jeff Hammel <k0scist@gmail.com>
date Wed, 09 Jul 2014 16:26:49 -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()