# HG changeset patch
# User Jeff Hammel <jhammel@mozilla.com>
# Date 1388434933 28800
# Node ID e3341b7ce4efd5428e1c9dae4446e81fce4c2f27
# Parent  7b70e5c0d4105d9153a6cfc45e44c85a210e4bd5
binarysearch

diff -r 7b70e5c0d410 -r e3341b7ce4ef python/example/binarysearch.py
--- /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()