Find integer in sorted list.

laurentluce · laurentluce · commit 88c4c61593e0 · 2015-11-16T09:39:45.000-05:00
diff --git a/README.md b/README.md
@@ -21,6 +21,13 @@ String matching
   - Knuth-Morris-Pratt
   - Boyer-Moore-Horspool
 
+Generators
+  - Permutations.
+
+Lists
+  - Subset with highest sum.
+  - Find integer in sorted list.
+
 ### Installation
 Get the source and run
 
diff --git a/algorithms/list.py b/algorithms/list.py
@@ -1,3 +1,28 @@
+def find_int(i, l):
+    """
+    Find integer in a sorted list.
+
+    Example: 4 in [1, 3, 4, 6, 7, 9] -> 2
+    @param i integer to find.
+    @param l sorted list.
+    @returns index if found, None if not.
+    """
+    if l:
+        p_idx = len(l) / 2
+        p = l[p_idx]
+        if i == p:
+            return p_idx
+        elif len(l) == 1:
+            return
+        elif i < p:
+            res = find_int(i, l[:p_idx])
+            if res:
+                return res
+        elif i > p:
+            res = find_int(i, l[p_idx:])
+            if res:
+                return res + p_idx
+
 def find_max_sub(l):
     """
     Find subset with higest sum
diff --git a/algorithms/tests/test_list.py b/algorithms/tests/test_list.py
@@ -6,11 +6,30 @@ class List(unittest.TestCase):
     def setUp(self):
         pass
 
-    def test_list(self):
+    def test_find_max_sub(self):
         bounds, m = [e for e in list.find_max_sub([-2, 3, -4, 5, 1, -5])]
         self.assertEqual(bounds, (3, 4))
         self.assertEqual(m, 6)
 
+    def test_find_int_first_half(self):
+        idx = list.find_int(4, [1, 2, 4, 5, 7, 9])
+        self.assertEqual(idx, 2)
+
+    def test_find_int_second_half(self):
+        idx = list.find_int(7, [1, 2, 4, 5, 7, 9])
+        self.assertEqual(idx, 4)
+
+    def test_find_int_not_found(self):
+        idx = list.find_int(3, [1, 2, 4, 5, 7, 9])
+        self.assertIsNone(idx)
+
+    def test_find_int_single_element_list(self):
+        idx = list.find_int(3, [3,])
+        self.assertEqual(idx, 0)
+
+    def test_find_int_empty_list(self):
+        idx = list.find_int(3, [])
+        self.assertIsNone(idx)
 
 if __name__ == '__main__':
   unittest.main()
