My simple solution that applies binary-search recursively


  • 0

    Here's the solution to part1 of this question:

        public int findMin(int[] nums) {
            int low = 0; int high = nums.length - 1;
            while (low < high) { // we bail when low == high
                int mid = low + (high - low) / 2;
                if (nums[mid] > nums[high]) low = mid + 1;
                else if (nums[mid] <= nums[high]) high = mid; // redundant/verbose if-check
            }
            return nums[low];
        }
    

    This can also be rewritten as:

        public int findMin(int[] nums) {
            return nums[findMinHelper(nums, 0, nums.length-1)];
        }
        public int findMinHelper(int[] nums, int low, int high) {
            if (low == high) return low;
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]) return findMinHelper(nums, mid + 1, high);
            else if (nums[mid] <= nums[high])  return findMinHelper(nums, low, mid);
        }
    

    The only difference in part2 is that when the middle element is the same as the high, we recursively check which half gives us the solution:

        public int findMin(int[] nums) {
            return nums[findMinHelper(nums, 0, nums.length-1)];
        }
        public int findMinHelper(int[] nums, int low, int high) {
            if (low == high) return low;
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]) return findMinHelper(nums, mid + 1, high);
            else if (nums[mid] < nums[high])  return findMinHelper(nums, low, mid);
            else {   // duplicate "handling" case
               int left = findMinHelper(nums, low, mid);
               int right = findMinHelper(nums, mid + 1, high);
               return nums[left] < nums[right] ? left : right;
            }
        }
    

    This is a mild optimization to some of the other solutions where you just move to the adjacent element (left) repetitively.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.