Return to Answer

bug fix

edited Apr 2, 2015 at 12:45

 public static int findReset(List<Integer> rotatedArray) { if (rotatedArray.isEmpty()) { throw new NoSuchElementException("No reset for an empty list"); } return findReset0(rotatedArray, 0, rotatedArray.size()); } private static int findReset0(List<Integer> rotatedArray, int left, int right) { // when array is already sorted if(left + 1 == right || rotatedArray.get(left) < rotatedArray.get(right - 1)) return left; int middle = (left + right) / 2; if (rotatedArray.get(left) <<= rotatedArray.get(middle - 1)) { // when left side is monotonically increasing return findReset0(rotatedArray, middle, right); } else { // when right side is monotonically increasing return findReset0(rotatedArray, left, middle); } }

 public static int findReset(List<Integer> rotatedArray) { if (rotatedArray.isEmpty()) { throw new NoSuchElementException("No reset for an empty list"); } int left = 0, right = rotatedArray.size(); while(left + 1 < right && rotatedArray.get(left) >= rotatedArray.get(right - 1)) { int middle = (left + right) / 2; if (rotatedArray.get(left) <<= rotatedArray.get(middle - 1)) { // when left side is monotonically increasing left = middle; } else { // when right side is monotonically increasing right = middle; } } return left; }

 public static int findReset(List<Integer> rotatedArray) { if (rotatedArray.isEmpty()) { throw new NoSuchElementException("No reset for an empty list"); } return findReset0(rotatedArray, 0, rotatedArray.size()); } private static int findReset0(List<Integer> rotatedArray, int left, int right) { // when array is already sorted if(left + 1 == right || rotatedArray.get(left) < rotatedArray.get(right - 1)) return left; int middle = (left + right) / 2; if (rotatedArray.get(left) < rotatedArray.get(middle - 1)) { // when left side is monotonically increasing return findReset0(rotatedArray, middle, right); } else { // when right side is monotonically increasing return findReset0(rotatedArray, left, middle); } }

 public static int findReset(List<Integer> rotatedArray) { if (rotatedArray.isEmpty()) { throw new NoSuchElementException("No reset for an empty list"); } int left = 0, right = rotatedArray.size(); while(left + 1 < right && rotatedArray.get(left) >= rotatedArray.get(right - 1)) { int middle = (left + right) / 2; if (rotatedArray.get(left) < rotatedArray.get(middle - 1)) { // when left side is monotonically increasing left = middle; } else { // when right side is monotonically increasing right = middle; } } return left; }

 public static int findReset(List<Integer> rotatedArray) { if (rotatedArray.isEmpty()) { throw new NoSuchElementException("No reset for an empty list"); } return findReset0(rotatedArray, 0, rotatedArray.size()); } private static int findReset0(List<Integer> rotatedArray, int left, int right) { // when array is already sorted if(left + 1 == right || rotatedArray.get(left) < rotatedArray.get(right - 1)) return left; int middle = (left + right) / 2; if (rotatedArray.get(left) <= rotatedArray.get(middle - 1)) { // when left side is monotonically increasing return findReset0(rotatedArray, middle, right); } else { // when right side is monotonically increasing return findReset0(rotatedArray, left, middle); } }

 public static int findReset(List<Integer> rotatedArray) { if (rotatedArray.isEmpty()) { throw new NoSuchElementException("No reset for an empty list"); } int left = 0, right = rotatedArray.size(); while(left + 1 < right && rotatedArray.get(left) >= rotatedArray.get(right - 1)) { int middle = (left + right) / 2; if (rotatedArray.get(left) <= rotatedArray.get(middle - 1)) { // when left side is monotonically increasing left = middle; } else { // when right side is monotonically increasing right = middle; } } return left; }

manual tail recursion optimization

Source Link

edited Apr 2, 2015 at 1:09

johnchen902

Here is a version with manual tail recursion optimization:

 public static int findReset(List<Integer> rotatedArray) { if (rotatedArray.isEmpty()) { throw new NoSuchElementException("No reset for an empty list"); } int left = 0, right = rotatedArray.size(); while(left + 1 < right && rotatedArray.get(left) >= rotatedArray.get(right - 1)) { int middle = (left + right) / 2; if (rotatedArray.get(left) < rotatedArray.get(middle - 1)) { // when left side is monotonically increasing left = middle; } else { // when right side is monotonically increasing right = middle; } } return left; }

Here is a version with manual tail recursion optimization:

 public static int findReset(List<Integer> rotatedArray) { if (rotatedArray.isEmpty()) { throw new NoSuchElementException("No reset for an empty list"); } int left = 0, right = rotatedArray.size(); while(left + 1 < right && rotatedArray.get(left) >= rotatedArray.get(right - 1)) { int middle = (left + right) / 2; if (rotatedArray.get(left) < rotatedArray.get(middle - 1)) { // when left side is monotonically increasing left = middle; } else { // when right side is monotonically increasing right = middle; } } return left; }

Source Link

answered Apr 2, 2015 at 0:46

johnchen902

The method should be static.
The method should throw NoSuchElementException when the list is empty.
I prefer to index by [left, right) instead of using subList
Choose a good pivot location, and you don't need the size() == 2.

In code:

 public static int findReset(List<Integer> rotatedArray) { if (rotatedArray.isEmpty()) { throw new NoSuchElementException("No reset for an empty list"); } return findReset0(rotatedArray, 0, rotatedArray.size()); } private static int findReset0(List<Integer> rotatedArray, int left, int right) { // when array is already sorted if(left + 1 == right || rotatedArray.get(left) < rotatedArray.get(right - 1)) return left; int middle = (left + right) / 2; if (rotatedArray.get(left) < rotatedArray.get(middle - 1)) { // when left side is monotonically increasing return findReset0(rotatedArray, middle, right); } else { // when right side is monotonically increasing return findReset0(rotatedArray, left, middle); } }