LeetCode.153.162(二分查找)

153.寻找旋转排序数组中的最小值

class Solution {
  public:
    int findMin(vector<int> &nums) {
        /*int left = 0, right = nums.size() - 1;
        while (right >= left) {
            int mid = left + (right - left) / 2;
            if (nums[left] > nums[mid])
                right = mid;
            else if (nums[right] < nums[mid])
                left = mid + 1;
            if (nums[left] <= nums[right])
                return nums[left];
        }
        return nums[left];*/
        // 150/150 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 78.78 % of cpp submissions (9.9 MB)
        int left = 0, right = nums.size() - 1;
        while (right > left) {
            int mid = left + (right - left) / 2;
            if (nums[right] > nums[mid])
                right = mid;
            else
                left = mid + 1;
        }
        return nums[left];
        // 150/150 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 80.88 % of cpp submissions (9.9 MB)
    }
};

162.寻找峰值

class Solution {
  public:
    /*int findPeakElement(vector<int> &nums) { return find(nums, 0, nums.size() - 1); }
    int find(vector<int> &nums, int left, int right) {
        while (right > left) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right] && nums[mid] > nums[left]) {
                int leftM = find(nums, left, mid);
                int rightM = find(nums, mid, right);
                if (leftM == mid) {
                    left = rightM;
                } else if (rightM == mid) {
                    left = leftM;
                } else
                    left = leftM;
            } else if (nums[right] >= nums[left])
                left = mid + 1;
            else if (nums[right] < nums[left])
                right = mid - 1;
        }
        return left;
        // 63/63 cases passed (4 ms)
        // Your runtime beats 67.65 % of cpp submissions
        // Your memory usage beats 94.96 % of cpp submissions (8.5 MB)
    }*/
    int findPeakElement(vector<int> &nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    // 63/63 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 84.49 % of cpp submissions (8.5 MB)
    //*找规律：
    //*规律一：如果nums[i] > nums[i+1]，则在i之前一定存在峰值元素
    //*规律二：如果nums[i] < nums[i+1]，则在i+1之后一定存在峰值元素
    //(=^=!)
};