图解「剑指Offer」之旋转数组的最小数字

2 years ago

source link: https://www.cxyxiaowu.com/463.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

图解「剑指Offer」之旋转数组的最小数字

剑指offer 2年前 0 2.8K

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

作者 | 程序员小吴

来源 | 五分钟学算法

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0，1，2，4，5，6，7] 可能变为 [4，5，6，7，0，1，2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3，4，5，1，2]
输出: 1

示例 2:

输入: [4，5，6，7，0，1，2]
输出: 0

最直接的方法是使用 暴力法：搜索整个数组，找到其中的最小元素，这样的时间复杂度是 O(N)，其中 N 是给定数组的大小。

这道题目可以使用 二分搜索 的思想进行解决。

找到数组的中间元素 mid。
如果中间元素 > 数组第 low 个元素，则在 mid 右边搜索变化点。
如果中间元素 < 数组第 high 个元素，则在 mid 左边搜索变化点。

//author:程序员小吴
class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            if (nums[low] < nums[high]) return nums[low];
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]){
               low = mid + 1; 
            } else{
               high = mid;
            } 
          }
        return nums[low];
    }
}