【LeetCode热题100】【二分查找】寻找旋转排序数组中的最小值

叶茂林

发布于 2024-04-17 08:05:38

540

发布于 2024-04-17 08:05:38

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

题目链接：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

要在一个561234这样的数组里面找最小值，注意每次二分可以拆出要么两个升序数组（456、123），要么拆出一个升序数组和一个具有同样性质的数组（561、234）

因为要找最小值，如果二分后左边有序，那么左边边的那个就是左边最小的，此时更小的只会出现在右边，继续二分右边；如果二分后左边无序，那么说明最小的一定出现在左边，继续二分左边的

在过程中更小最小值

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

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-16，如有侵权请联系 cloudcommunity@tencent.com 删除

leetcode