@Test public void testMagicIndex() { int[] array = new int[] { -1, 0, 2 }; assertEquals(2, magicIndex(array, 0, array.length)); array = new int[] { 1, 2, 3 }; assertEquals(-1, PracticeQuestionsCh9.magicIndex(array, 0, array.length)); }
public static int magicIndex(int[] array, int startIndex, int endIndex) { if (startIndex >= endIndex) { return -1; } long avg = startIndex + endIndex >> 1; if (avg >= Integer.MAX_VALUE) { return -1; } int midIdx = (int) avg; int val = array[midIdx]; if (val == midIdx) { LOGGER.debug("Found magic index{}.%n", midIdx); return midIdx; } LOGGER.debug("Start index = {}, end index = {}, middle index = {}.%n", startIndex, endIndex, midIdx); LOGGER.debug("val = {}.%n", val); if (midIdx < val) { return magicIndex(array, startIndex, --midIdx); } return magicIndex(array, ++midIdx, endIndex); }
PracticeQuestionsCh9 { public static int magicIndex(int[] array, int startIndex, int endIndex) { if (startIndex >= endIndex) { return -1; } long avg = startIndex + endIndex >> 1; if (avg >= Integer.MAX_VALUE) { return -1; } int midIdx = (int) avg; int val = array[midIdx]; if (val == midIdx) { LOGGER.debug("Found magic index{}.%n", midIdx); return midIdx; } LOGGER.debug("Start index = {}, end index = {}, middle index = {}.%n", startIndex, endIndex, midIdx); LOGGER.debug("val = {}.%n", val); if (midIdx < val) { return magicIndex(array, startIndex, --midIdx); } return magicIndex(array, ++midIdx, endIndex); } }
PracticeQuestionsCh9 { public static int magicIndex(int[] array, int startIndex, int endIndex) { if (startIndex >= endIndex) { return -1; } long avg = startIndex + endIndex >> 1; if (avg >= Integer.MAX_VALUE) { return -1; } int midIdx = (int) avg; int val = array[midIdx]; if (val == midIdx) { LOGGER.debug("Found magic index{}.%n", midIdx); return midIdx; } LOGGER.debug("Start index = {}, end index = {}, middle index = {}.%n", startIndex, endIndex, midIdx); LOGGER.debug("val = {}.%n", val); if (midIdx < val) { return magicIndex(array, startIndex, --midIdx); } return magicIndex(array, ++midIdx, endIndex); }  }
PracticeQuestionsCh9 { public static int magicIndex(int[] array, int startIndex, int endIndex) { if (startIndex >= endIndex) { return -1; } long avg = startIndex + endIndex >> 1; if (avg >= Integer.MAX_VALUE) { return -1; } int midIdx = (int) avg; int val = array[midIdx]; if (val == midIdx) { LOGGER.debug("Found magic index{}.%n", midIdx); return midIdx; } LOGGER.debug("Start index = {}, end index = {}, middle index = {}.%n", startIndex, endIndex, midIdx); LOGGER.debug("val = {}.%n", val); if (midIdx < val) { return magicIndex(array, startIndex, --midIdx); } return magicIndex(array, ++midIdx, endIndex); }  static int magicIndex(int[] array, int startIndex, int endIndex); static Set<String> perm(String s); }
PracticeQuestionsCh9 { public static int magicIndex(int[] array, int startIndex, int endIndex) { if (startIndex >= endIndex) { return -1; } long avg = startIndex + endIndex >> 1; if (avg >= Integer.MAX_VALUE) { return -1; } int midIdx = (int) avg; int val = array[midIdx]; if (val == midIdx) { LOGGER.debug("Found magic index{}.%n", midIdx); return midIdx; } LOGGER.debug("Start index = {}, end index = {}, middle index = {}.%n", startIndex, endIndex, midIdx); LOGGER.debug("val = {}.%n", val); if (midIdx < val) { return magicIndex(array, startIndex, --midIdx); } return magicIndex(array, ++midIdx, endIndex); }  static int magicIndex(int[] array, int startIndex, int endIndex); static Set<String> perm(String s); static final Logger LOGGER; }