1 files changed, 33 insertions, 0 deletions
diff --git a/scratch/facebook/recursion-and-dynamic-programming/magic-index.py b/scratch/facebook/recursion-and-dynamic-programming/magic-index.py
new file mode 100644
index 000000000000..03b2de015dfe
--- /dev/null
+++ b/scratch/facebook/recursion-and-dynamic-programming/magic-index.py
@@ -0,0 +1,33 @@
+from math import floor
+
+def find_magic_index_brute(xs):
+    for i in range(len(xs)):
+        if xs[i] == i:
+            return i
+    return -1
+
+def mid(lo, hi):
+    return lo + floor((hi - lo) / 2)
+
+def find_magic_index(xs):
+    lo, hi = 0, len(xs) - 1
+    return do_find_magic_index(xs, 0, len(xs) - 1)
+
+def do_find_magic_index(xs, lo, hi):
+    pass
+
+xss = [
+    [],
+    [-1,0,2,4,5,6],
+    [1,1,1,1,1,5],
+    [-2,-2,-2,-2,4],
+    [1,2,3,4,5],
+]
+
+for xs in xss:
+    print(xs)
+    a = find_magic_index_brute(xs)
+    b = find_magic_index(xs)
+    print(a, b)
+    assert a == b
+    print("Success!")