C++ very very easy-understanding using binary search


  • 0
    X
    class Solution {
    public:
        int findMin(vector<int>& nums) {
            if(nums.size() == 0){
                return -1;
            }
            int low = 0, high = nums.size() - 1;
            int ans = nums[low];
            while(low <= high){
                int mid = low + (high - low) / 2;
                // remove a tricky case, for example 10 3 10 10 10
                if(low < mid && mid < high && nums[low] == nums[mid] && nums[high] == nums[mid]){
                    ++low;
                    --high;
                }
                else if (nums[low] <= nums[mid]) {//first half is in order
                    ans = nums[low] < ans ? nums[low] : ans;
    				low = mid + 1;
    			}
    			else {// second half is in order
    				ans = nums[mid] < ans ? nums[mid] : ans;
    				high = mid - 1;
    			}
            }
            return ans;
        }
    };

Log in to reply
 

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