Share my simple java binary search solution


  • 0
    L

    The idea is straightforward.
    We first check if left sub half is continuous,

    • if so, we compare left end with right end,
      if left end is greater than right end, it means that we have rotated the array here and given that nums[l] < nums[mid] (continuous left half) and nums[l] > nums[r], apparently the min should be in the right half.
    • If left is smaller, than we know no rotation here and left is just the min.

    if the left half is not continuous, then the left half must have a 'drop' in between, and we just need to continue to search (left, mid)

    class Solution {
        public int findMin(int[] nums) {
            if (nums.length == 1) return nums[0];
            if (nums.length == 2) return Math.min(nums[0], nums[1]);
            
            int l = 0, r = nums.length - 1;
            int min = Integer.MAX_VALUE;
            
            while (l + 1 < r) {
                int mid = l + (r - l) / 2;
                if (nums[l] < nums[mid]) { // continous left
                    if (nums[l] > nums[r]) { // right end smaller
                        min = Math.min(nums[r], min);
                        l = mid;
                    } else {
                        return nums[l];
                    }
                } else {
                    min = Math.min(min, nums[mid]);
                    r = mid;
                }
            }
            
            return min = Math.min(nums[l], nums[r]);
        }
    }
    

Log in to reply
 

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