山东滨州疫情最新消息_seo优化价格_肥城市区seo关键词排名_seo目标关键词优化

---

题目链接：

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

---

题目描述：

---

解法

暴力解法：O(n)

从前往后找数组中的最小值。

二分算法：O(logn)

先找二段性

因为这里的数是全部不相同的，所以可以这么搞。

以D点作为参照物：

AB里面每一个值都>D，CD里面每一个值都<=D

所以，最小值就是C点所在的位置。

A~B：nums[i]>nums[n-1]

C~D：nums[i]<=nums[n-1]

---

C++ 算法代码：

class Solution 
{public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1;int x = nums[right]; // 标记一下最后一个位置的值while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > x) left = mid + 1;else right = mid;}return nums[left];}
};

---

图解

例如：nums = [3,4,5,1,2]

1. left = 0, right =4

   x=nums[4]=2

   进入循环，mid = 2

   nums[mid] > x，left=3

2. left = 3, right =4

   进入循环，mid = 3

   right = 3

3. 结束程序，返回1