Java solution with binary search


  • 29
    C

    The minimum element must satisfy one of two conditions: 1) If rotate, A[min] < A[min - 1]; 2) If not, A[0]. Therefore, we can use binary search: check the middle element, if it is less than previous one, then it is minimum. If not, there are 2 conditions as well: If it is greater than both left and right element, then minimum element should be on its right, otherwise on its left.

    public class Solution {
        public int findMin(int[] num) {
            if (num == null || num.length == 0) {
                return 0;
            }
            if (num.length == 1) {
                return num[0];
            }
            int start = 0, end = num.length - 1;
            while (start < end) {
                int mid = (start + end) / 2;
                if (mid > 0 && num[mid] < num[mid - 1]) {
                    return num[mid];
                }
                if (num[start] <= num[mid] && num[mid] > num[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            return num[start];
        }
    }

  • -25
    R

    {
    class Solution {
    public:
    int findMin(vector<int> &num) {
    sort(num.begin(),num.end());
    return num[0];
    }
    };
    }


  • 0
    B

    Why have O(nlogn) when you can do it in log(n)


  • 13
    P
    public class Solution {
        public int findMin(int[] nums) {
            int lo = 0, hi = nums.length - 1;
            if (nums[hi] > nums[lo]) return nums[lo];
            while (hi - lo > 1) {
                int mid = lo + (hi - lo) / 2;
                if (nums[mid] < nums[lo]) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            }
            return Math.min(nums[lo],nums[hi]);
        }
    }

  • 1
    S

    Nice answer! One thing want to point out is when calculating mid, (start + end) may potentially over flow. So like the first answer below using
    mid = lo + (hi - lo) / 2;
    would avoid that.


  • 0
    Y

    Nice solution! I'm confused about this sentence "end=mid-1" why not return start=mid-1. For example '6 7 0 1 2 4 5': mid is 1, and when start=mid-1, return nums[start]=0


  • 18
    B
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
    

    simpler Java code


  • 0
    F
        public int findMin(int[] nums) {
            int previous=nums[0];
            for(int i=1;i<nums.length;i++)
            {
                if(previous>nums[i])
                    return nums[i];
                else
                {
                    previous=nums[i];
                }
            }
            return nums[0];
        }
    }
    

    any thing wrong with this one?


  • 0
    S

    @petrichory said in Java solution with binary search:

    int lo = 0, hi = nums.length - 1;
    if (nums[hi] > nums[lo]) return nums[lo];
    while (hi - lo > 1) {
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] < nums[lo]) {
    hi = mid;
    } else {
    lo = mid;
    }
    }
    return Math.min(nums[lo],nums[hi]);

    for case {3,2,1}, this returns 2, but it passes OJ. Could you double check this?


  • 0
    X

    My version. Hope it helps

    public class Solution {
        public int findMin(int[] nums) {
            int left = 0, right = nums.length-1;
            while(left < right){
                if(nums[left] < nums[right])
                    break;
                int mid = (left + right)/2;
                if(nums[mid] > nums[right]){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }
            return nums[left];
        }
    }
    

  • 0
    R

    I don't think the check for num[start] <= num[mid] is necessary, if num[mid] > num[end], it will always be the case that the minimum element will be on the right half.

    My code:

    public class Solution {
        public int findMin(int[] nums) {
            int min = nums[0];
            
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                
                if (nums[right] < nums[mid])
                    left = mid + 1;
                else if (mid > left && nums[mid - 1] < nums[mid])
                    right = mid - 1;
                else {
                    min = nums[mid];
                    break;
                }
            }
            
            return min;
        
        }
    }
    
    

Log in to reply
 

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