1.1 寻找旋转排序数组中的最小值（无重复元素）
已知一个长度为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)的算法解决此问题。
如果数组经过旋转，那么此时数组肯定被分为两个递增的区间，并且第一个区间的最小值nums[0]大于第二个区间的最大值nums[nums.size()-1]，我们只需要与nums[nums.size()-1]做判断就可以知道nums[mid]所处的区间，进而进行二分。
intfindMin(vector<int>&nums){intlast=nums.back();if(nums[0]<=last)returnnums[0];// 没有旋转intl=0,r=nums.size()-1;while(l<r){intmid=l+r>>1;// 在左边的有序区间if(nums[mid]>last)l=mid+1;// 在右边的有序区间elser=mid;}returnnums[l];}补充，如何找到最大值？
思路和最小值相同，如果数组没有旋转，那么最大值就是nums[nums.size()-1]，否则，最大值就是第一段的最后一个元素：
intfindMax(vector<int>&nums){intlast=nums.back();// 没有旋转if(nums[0]<=last)returnnums[0];intl=0,r=nums.size()-1;while(l<r){intmid=l+r+1>>1;// 在左边的有序区间if(nums[mid]>last)l=mid;// 在右边的有序区间elser=mid-1;}returnnums[l];}1.2 寻找旋转排序数组中的最小值（有重复元素）
相较于上一题的不同之处是，这里存在重复元素。因此上一题的做法在这里就不适用了，例如3 1 3这个序列，如果使用上一题的方法，所得最小值为3，这是因为在我们的二分逻辑中，我们假设当nums[mid]==lsat时，mid 一定在旋转数组的第二部分也即第二个递增序列当中，但在这里显然不是的，如果 mid 为 0，那么实际上 mid 是在第一个递增序列中，也即旋转的数组的左半部分，也即此时应该进入l=mid的逻辑。
因此说，对于上一题的代码，如果应用在这里，当nums[mid]==last时，我们无法判断，当前 mid 到底是在第一个递增序列，还是第二个递增序列当中，这是根本的问题所在。
但实际上，如果出现nums[mid]==last的情况，由于我们只需要取最小值，所以我们这里实际上是可以忽略 last 的，因此此时数组中已经有一个等于 last 的元素值了，所以我们可以缩小 nums 的右边界。
也即，我们只需要基于上面的代码，修改一下nums[mid]==nums[r]的逻辑即可：
classSolution{public:intfindMin(vector<int>&nums){intl=0,r=nums.size()-1;while(l<r){intmid=l+r>>1;// 注意是与 nums[r] 比较大小if(nums[mid]==nums[r])r--;// 在左边区间elseif(nums[mid]>nums[r])l=mid+1;// 在右边区间elser=mid;}returnnums[l];}};需要注意的一个细节是，我们不是比较nums[mid]与nums.back()（不变）的大小，而是比较nums[mid]与nums[r]（动态变化）的大小。因为随着我们的r--，右边界是变化了的。
2.1 搜索旋转排序数组（无重复元素）
整数数组nums按升序排列，数组中的值互不相同。
在传递给函数之前，nums在预先未知的某个下标k（0 <= k < nums.length）上进行了向左旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。例如，[0,1,2,4,5,6,7]下标3上向左旋转后可能变为[4,5,6,7,0,1,2]。
给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。
你必须设计一个时间复杂度为O(log n)的算法解决此问题。
思路也很简单：
- 我们通过 mid 对
[l,r]这个区间进行二分产生两个子区间[l,mid]和[mid+1,r]，那么 target 必然在这其中一个区间当中（题目保证不存在重复元素）。 - 由于旋转的影响，这两个区间不一定都是有序的，但我们可以保证，至少有一个区间是有序的（易证），因此我们可以判断哪一个区间是有序的，然后再判断 target 是否在该区间当中，如果不在该区间，那么必然在另外一个区间当中（或者不存在）。
classSolution{public:intsearch(vector<int>&nums,inttarget){intl=0,r=nums.size()-1;while(l<r){intmid=l+r>>1;// 根据 mid 将 [l,r] 划分为: [l,mid], [mid+1,r]if(nums[l]<nums[mid]){// [l,mid] 有序if(nums[l]<=target&&target<=nums[mid])r=mid;elsel=mid+1;}else{// [mid+1,r] 有序if(nums[mid+1]<=target&&target<=nums[r])l=mid+1;elser=mid;}}returnnums[l]==target?l:-1;}};2.2 搜索旋转排序数组（有重复元素）
不存在重复元素时：
- 如果
nums[l] < nums[mid]，左半区间有序； - 如果
nums[mid + 1] < nums[r]，右半区间有序；
我们无需考虑nums[l] == nums[mid]的情况。
现在考虑重复元素也就是要考虑到nums[l] == nums[mid]时，到底是左半区间有序，还是右半区间有序，还是都有序，还是都无序😀。
- 考虑
[1,3,1,1,1]这个序列（l=0, r=4, mid=2），划分出的区间为[0,2]和[3,4]，此时左半区间不是有序的； - 考虑
[1,1,1,3,1]这个序列（l=0, r=4, mid=2）,划分出的区间为[0,2]和[3,4]，此时右半区间不是有序的；
因此说，对于nums[l] == nums[mid]的情况，我们必须要特殊处理。很简单，参考 [寻找旋转数组中最小值] 中处理重复元素的思想即可，当nums[l] == nums[mid]时，考虑到nums[l]和nums[mid]重复，我们可以直接收缩左边界l ++：
classSolution{public:boolsearch(vector<int>&nums,inttarget){intl=0,r=nums.size()-1;while(l<r){intmid=l+r>>1;// [l,mid], [mid+1,r]if(nums[l]<nums[mid]){// 左半区间有序if(nums[l]<=target&&target<=nums[mid])r=mid;elsel=mid+1;}// 注意这里我们不能写 else if(nums[mid + 1] < nums[r])// 否则下面的 else 就筛选不出 nums[l] == nums[mid] 的情况elseif(nums[l]>nums[mid]){// 左半区间无序并且 nums[l] != nums[mid] --> 右半区间有序if(nums[mid+1]<=target&&target<=nums[r])l=mid+1;elser=mid;}// 此时 nums[l] == nums[mid]elsel++;// 不清楚那边有序，直接收缩左边界}returnnums[l]==target;}};好的，如果你提交代码，会在下面这种测试用例下解答错误：
nums=[2,5]target=2问题在于: 当nums[mid] == nums[l]时，直接++l可能会跳过目标值！
知道了问题出在哪里，如果解决就很简单了，当nums[l] == nums[mid]时，我们只需要额外判断当前需要跳过的元素是否就是 target 即可：
classSolution{public:boolsearch(vector<int>&nums,inttarget){intl=0,r=nums.size()-1;while(l<r){intmid=l+r>>1;// [l,mid], [mid+1,r]if(nums[l]<nums[mid]){// 左半区间有序if(nums[l]<=target&&target<=nums[mid])r=mid;elsel=mid+1;}// 注意这里我们不能写 else if(nums[mid + 1] < nums[r])// 否则下面的 else 就筛选不出 nums[l] == nums[mid] 的情况elseif(nums[l]>nums[mid]){// 左半区间无序并且 nums[l] != nums[mid] --> 右半区间有序if(nums[mid+1]<=target&&target<=nums[r])l=mid+1;elser=mid;}// 此时 nums[l] == nums[mid]else{if(nums[l]==target)returntrue;l++;// 不清楚那边有序，直接收缩左边界}}returnnums[l]==target;}};当然我们也可以把代码修改成收缩右边界的形式，道理都是相同的：
// 收缩右边界boolsearch(vector<int>&nums,inttarget){intl=0,r=nums.size()-1;while(l<r){intmid=l+r>>1;// [l,mid], [mid+1,r]if(nums[mid+1]>nums[r]){// 右半区间无序并且 nums[mid + 1] != nums[r] --> 左半区间有序if(nums[l]<=target&&target<=nums[mid])r=mid;elsel=mid+1;}elseif(nums[mid+1]<nums[r]){if(nums[mid+1]<=target&&target<=nums[r])l=mid+1;elser=mid;}// 此时 nums[mid + 1] == nums[r]else{if(nums[r]==target)returntrue;r--;// 不清楚那边有序，直接收缩右边界}}returnnums[l]==target;}最后，需要注意的是，本题在极端情况下（数组所有元素相同且不为 target）的时间复杂度是O(N)级别的。
2.3 搜索旋转排序数组（有重复元素）（返回索引最小的）
相较于上一题，本体多了一个要求，那就是如果有多个元素等于 target，需要返回最小的 index。
参考：armeria
// ref: armeriaclassSolution{public:intsearch(vector<int>&nums,inttarget){intl=0,r=nums.size()-1;if(r==-1)return-1;while(l<r){intmid=l+r>>1;// [l,mid], [mid+1,r]if(nums[l]<nums[mid]){// 左边区间升序// 当左边区间升序时，并且 target 在左边区间，我们可以直接收缩右边界；// 如果不在左边区间，我们也可以直接拓展左边界if(nums[l]<=target&&target<=nums[mid])r=mid;elsel=mid+1;}elseif(nums[l]>nums[mid]){// 右半边升序// 当右边区间升序时，如果 target 在右边区间，我们不可以直接收缩左边界，因为此时 target 也可能在左边区间// 所以这里我们仍然需要判断，target 是否可能存在于左边区间// 以 [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14] 为例，我们假设 nums[mid] = 3，将数组划分为：// [15, 16, 19, 20, 25, 1, 3], [4, 5, 7, 10, 14]// 可以判断，当 target >= nums[l] || target <= nums[mid] 时，target 只能在左半天；否则，必然不存在于左半边if(target>=nums[l]||target<=nums[mid])r=mid;elsel=mid+1;}else{// nums[l] == nums[mid])if(nums[l]==target)r=l;// 注意此时不能直接返回 l，我们要继续收缩右边界elsel++;}}return(nums[l]==target)?l:-1;}};
完全指南：从打开到编辑的实用教程)
