153. 寻找旋转排序数组中的最小值(二分查找)(153. Find the minimum value in the rotation sort array (binary search))

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

n
1
n
nums = [0,1,2,4,5,6,7]
  • 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]

注意,数组  旋转一次 的结果为数组  。

[a[0], a[1], a[2], ..., a[n-1]]
[a[n-1], a[0], a[1], a[2], ..., a[n-2]]

给你一个元素值 互不相同 的数组  ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

nums

你必须设计一个时间复杂度为  的算法解决此问题。

O(log n)

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。

示例 3:

输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

提示:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组,并进行了 1 至 n 次旋转
 1 class Solution {
 2 public:
 3     int findMin(vector<int>& nums) {
 4         int left = 0;
 5         int right = nums.size() - 1;
 6         while (left < right) {
 7             int mid = left + (right - left) / 2;
 8             if (nums[mid] < nums[right]) { // 最小值在左边
 9                 right = mid;
10             } else { // 最小值在右边
11                 left = mid + 1;
12             }
13         }
14         return nums[left];
15     }
16 };
————————

153. Find the minimum value in the rotation sort array

n
1
n
nums = [0,1,2,4,5,6,7]
  • If you rotate it four times, you can get [4,5,6,7,0,1,2]
  • If you rotate it seven times, you can get [0,1,2,4,5,6,7]

Note that the array , is rotated once, and the result of , is an array.

[a[0], a[1], a[2], ..., a[n-1]]
[a[n-1], a[0], a[1], a[2], ..., a[n-2]]

Give you an array with element values , which are different from each other. It was originally an array arranged in ascending order and rotated many times according to the above situation. Please find and return the smallest element in the array.

nums

You must design an algorithm with a time complexity of {to solve this problem.

O(log n)

Example 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

Example 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。

Example 3:

输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

Tips:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All integers , in num , are different from each other
  • Num s , was originally an array sorted in ascending order and rotated , 1 , to , n , times
 1 class Solution {
 2 public:
 3     int findMin(vector<int>& nums) {
 4         int left = 0;
 5         int right = nums.size() - 1;
 6         while (left < right) {
 7             int mid = left + (right - left) / 2;
 8             if (nums[mid] < nums[right]) { // 最小值在左边
 9                 right = mid;
10             } else { // 最小值在右边
11                 left = mid + 1;
12             }
13         }
14         return nums[left];
15     }
16 };