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

原题链接

使用的方法

二分查找

解题思路

• 给定一个旋转排序数组，找出其中最小的元素。
• 由于数组是旋转排序的，我们可以使用二分查找来高效地找到最小元素的位置。
• 在二分查找的过程中，我们需要判断当前中间元素与右边界元素的关系。根据中间元素与右边界元素的关系，我们可以确定最小元素所在的区间。
• 如果中间元素小于右边界元素，说明最小元素在左半部分，我们将右边界移动到中间元素的位置；
• 如果中间元素大于右边界元素，说明最小元素在右半部分，我们将左边界移动到中间元素的下一个位置。
• 通过不断地将搜索范围缩小，我们可以快速地找到最小元素的位置或者者确定它不存在于数组中。

代码实现

class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while(low < high){
            int mid = low + (high - low)/2; // 防止 low + high 出现数值溢出
            if(nums[mid] < nums[high]){
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return nums[low];
    }
}