Mercurial > hg > config
changeset 566:e3341b7ce4ef
binarysearch
author | Jeff Hammel <jhammel@mozilla.com> |
---|---|
date | Mon, 30 Dec 2013 12:22:13 -0800 |
parents | 7b70e5c0d410 |
children | 67e5137b1476 |
files | python/example/binarysearch.py |
diffstat | 1 files changed, 38 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/example/binarysearch.py Mon Dec 30 12:22:13 2013 -0800 @@ -0,0 +1,38 @@ +#!/usr/bin/env python + +def find_index(ordered_array, to_find): + """ + Return index of ``to_find`` via binary search. + Returns None if not in ``ordered_array`` + + ordered_array -- array of ordered values + to + """ + if not ordered_array: + return + minimum = 0 + maximum = len(ordered_array)-1 + while True: + middle = (minimum + maximum)/2 + value = ordered_array[middle] + if value == to_find: + return middle + if maximum == minimum: + return + if value < to_find: + minimum = middle+1 + continue + if value > to_find: + maximum = middle + continue + +if __name__ == '__main__': + import unittest + + class TestFindIndex(unittest.TestCase): + values = [1,2,4,8,16,17] + def test_spotcheck(self): + for index, value in enumerate(self.values): + self.assertEqual(find_index(self.values, value), index) + + unittest.main()