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

1. 题目链接 https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

2. 题目描述

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

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

      请找出其中最小的元素。

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

   2. 示例 1:

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

      示例 2:

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

3. 解题思路

   1. 二分查找。创建两个指针变量low,high，分别指向0， 和nums.size() - 1。取重点m，若nums[m] > nums[high]那么最小元一定位于（m, h]，否则，最小元一定位于[low, m]。

4. 代码

   1. python

      class Solution:
          def findMin(self, nums) -> int:
              l, h = 0, len(nums) - 1
              while l < h:
                  m = (l + h) // 2
                  if nums[m] > nums[h]:
                      l = m + 1
                  else:
                      h = m
              return nums[l]

       

   2. c++

      class Solution {
      public:
          int findMin(vector<int>& nums) {
              int l = 0, h = nums.size() - 1;
              while (l < h){
                  int m = l + (h-l) / 2;
                  if (nums[m] > nums[h])
                      l = m + 1;
                  else
                      h = m;
              }
              return nums[l];
          }
      };