Find Minimum in Rotated Sorted Array

This problem is a series problems that have a little difficulty. The main difficulty not only exists in thinking of the idea to solve it, but also in implementing it correctly with out bug. The solution to this series of problems makes use of the same idea as binary search, so it is very important to handle search boundary correctly to avoid infinite looping and wrong answer.

No duplicated elements

If there is no duplicated elements in the array, the program will be much like that of binary search. In this case, we have only one minimal element . At first we pick a boundary and and make sure . Let , if , we know that , or there must have . To avoid infinite looping, we have to keep:

  1. After each iteration, we still have .
  2. After each iteration, is less than before

We let when and let when otherwise. As there always be when , so will become less and less and the loop must have an end.

public class FindMiniumInRotatedSortedArray {
    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int mid;

        while (l < r) {
            mid = (l + r) / 2;
            if (nums[mid] < nums[r]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return nums[l];
    }
}

Allow duplicated elements

If duplicated elements is allowed, the problem becomes a little more complex and we cannot implement it without recursion. The reason is that, if , the minimal number may appears both in or . The cases is also a little more difficult to discuss. we disscuss all cases below:

  1. : the same as before, the minimal element must be in
  2. : the same as before, the minimal element must be in
  3. : there are several different cases respect to different relationship between and
    1. : both and is possible.
    2. : must be in
    3. : must be in

We find that the only difference comes when , and if , we should put union into the case of . So the solution is:

public class FindMiniumInRotatedSortedArray {
    private int findMin(int[] nums, int l, int r) {
        if (l >= r) return nums[l];

        int mid = (l + r) / 2;

        if (nums[mid] == nums[r] && nums[mid] == nums[l]) {
            return Math.min(findMin(nums, l, mid), findMin(nums, mid + 1, r));
        } else if (nums[mid] <= nums[r]) {
            return findMin(nums, l, mid);
        } else {
            return findMin(nums, mid + 1, r);
        }
    }

    public int findMin(int[] nums) {
        return findMin(nums, 0, nums.length - 1);
    }
}