Skip to main content
bug fix
Source Link
johnchen902
  • 358
  • 1
  • 11
    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
johnchen902
  • 358
  • 1
  • 11

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
johnchen902
  • 358
  • 1
  • 11

  1. The method should be static.
  2. The method should throw NoSuchElementException when the list is empty.
  3. I prefer to index by [left, right) instead of using subList
  4. 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);
        }
    }