| 16 | } |
| 17 | |
| 18 | public static int magicFast(int[] array, int start, int end) { |
| 19 | if (end < start || start < 0 || end >= array.length) { |
| 20 | return -1; |
| 21 | } |
| 22 | int midIndex = (start + end) / 2; |
| 23 | int midValue = array[midIndex]; |
| 24 | if (midValue == midIndex) { |
| 25 | return midIndex; |
| 26 | } |
| 27 | /* Search left */ |
| 28 | int leftIndex = Math.min(midIndex - 1, midValue); |
| 29 | int left = magicFast(array, start, leftIndex); |
| 30 | if (left >= 0) { |
| 31 | return left; |
| 32 | } |
| 33 | |
| 34 | /* Search right */ |
| 35 | int rightIndex = Math.max(midIndex + 1, midValue); |
| 36 | int right = magicFast(array, rightIndex, end); |
| 37 | |
| 38 | return right; |
| 39 | } |
| 40 | |
| 41 | public static int magicFast(int[] array) { |
| 42 | return magicFast(array, 0, array.length - 1); |