Why couldn't the magic index be on the left side? Observe that when we move from i to i -1, the value at this index must decrease by at least 1, if not more (since the array is sorted and all the elements are distinct). So, if the middle element is already too small to be a magic index, then when we move to the left, subtracting k indexes and (at least) k values, all subsequent elements will also be too small. We continue to apply this recursive algorithm, developing code that looks very much like binary search. 1 2 3 4 5 6 7 8 9 10 11 12 int magicFast(int[] array) { return magicFast(array) 0) array. length 1); } int magicFast(int[] array) int start) int end) { if (end < start) { return -1; } int mid = (start + end) / 2; if (array[mid] == mid) { return mid; } else if (array[mid] > mid){ 346 Cracking the Coding Interview, 6th Ed ition pg 135 Solutions to Chapter 8 I Recursion and Dynamic Programming 13 14 15 16 17 } ret urn magicFast(array, start, mid 1); } else {

If the elements are not distinct, then this algorithm fails. Consider the following array: When we see that A [mid] < mid, we cannot conclude which side the magic index is on. It could be on the right side, as before. Or, it could be on the left side (as it, in fact, is). Could it be anywhere on the left side? Not exactly. Since A = 3, we know that A [ 4] couldn't be a magic index. A [ 4] would need to be 4 to be the magic index, but A [ 4 ] must be less than or equal to A . In fact, when we see that A = 3, we'll need to recursively search the right side as before. But, to search the left side, we can skip a bunch of elements and only recursively search elements A [e] through A . A[ 3] is the first element that could be a magic index.

The general pattern is that we compare mid Index and midValue for equality first. Then, if they are not equal, we recursively search the left and right sides as follows: Left side: search indices start through Math. min (mid Index 1, midValue) . Right side: search indices Math. max (mid Index + 1, midVa lue) through end. The code below implements this algorithm. int magi cFast(int[] array) { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 } retur n magicFast(array, e, array. length 1 ); } int magi cFast(int[] array, int start, int end) { if (end < start) return -1; i nt mi dlndex = (start + end ) / 2; int mi dValue = a r ray[midlndex]; if (mi dValue == midlndex) {

min(midlndex 1, midvalue); int l eft = magicFast(array, start, leftlndex); if (l eft >= 0) { ret urn left; } / * Se arch right int r i ghtlndex = Math.max(midlndex + 1, midValue); i nt right = magicFast(array, rightlndex, end); retu rn right; CrackingTheCodinglnterview.com 16th Edition 347 Solutions to Chapter 8 I Recursion and Dynamic Programming Note that in the above code, if the elements are all distinct, the method operates almost identically to the first solution. 8.4 Power Set: Write a method to return all subsets of a set. pg 135