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