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

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

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

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

( 例如，数组 [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

方法：二分查找

思路：通过二分查找缩小区间查找，每次缩小一半，如果中间的元素小于或等于右边界元素则将右边界往中间移（由于此时中间元素可能是唯一的最小元素所以直接将右边界移至中间即可），否则将左边界往中间移（此时中间元素不可能是唯一的最小元，所以可将左边界移至中间加1元素处），当左边界等于右边界时，此元素即为最小元素。

运行数据：执行用时：0 ms，内存消耗：39.3 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// LeetCode指定调用方法
public int findMin(int[] nums) {

    int l = 0;
    int r = nums.length - 1;

    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] <= nums[r]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    return nums[l];
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！