subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226

git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789

1 files changed, 33 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/magic-index.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/magic-index.py
new file mode 100644
index 000000000000..03b2de015dfe
--- /dev/null
+++ b/users/wpcarro/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!")