Java binary search log(n) solution


  • 0
    Y

    To improve the time complexity of the brute force approach, we can use the binary search method. The array is a rotating array in ascending order, so the numbers in the array before minimum are all larger than the last number of the array. Similarly, the numbers in the array after the minimum are all smaller than the last number of the array. Therefore, we could separate the array into two parts, and the answer we want is the dividing line.

        public int findMin(int[] nums) {
            int l = 0, r = nums.length - 1;
            while (l < r - 1) {
                int mid = l + (r - l) / 2;
                if (nums[mid] > nums[nums.length - 1]) {
                    l = mid;
                } else if (nums[mid] < nums[nums.length - 1]) {
                    r = mid;
                }
            }
            return nums[l] < nums[r] ? nums[l] : nums[r];
        }
    

    Complexity Analysis
    Time complexity : O(log(n))
    Space complexity: O(1)


Log in to reply
 

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