[java/0ms] compared with prob 162: global base vs. local base.


  • 0

    This idea is coming from problem 162, while here we want to find the base instead of peak. So we can assume: nums[-1] = +inf. nums[length+1] = +inf. I made a mistake using local optimum way to solve this by using nums[mid] < nums[mid+1].

    If we use nums[mid] < nums[mid+1], we can definitely find a base, but it's a local base. However, we have to find the lowest base, the global base.

    How we can find the smallest? Compare with the first element. : )

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

Log in to reply
 

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