力扣HOT100之二分查找：33. 搜索旋转排序数组

这道题第一次做，没什么思路，直接去看灵神的题解了，看完题解才发现需要先做153. 寻找旋转排序数组中的最小值作为前置题，有了这道题的基础以后做本题就比较轻松了。这里先简单说一下寻找旋转排序数组中的最小值。题目如下：

我们阅读完题目不难看出，经过旋转后，数组nums有两种可能的状态：

1. nums被分为两个局部有序的子数组，每一个子数组都是严格递增的，此时第一个数组中的所有值均大于第二个数组中的最大值；
2. nums依旧保持整体有序
   因此我们需要利用二分查找来判断，定义left = 0，right = nums.size() - 1，使用左闭右开的搜索范围（[left, right)），注意，此时nums的最后一个元素始终都不在查找范围内，因为我们需要不断将中间值与num最后一个元素进行比较，以确定最小值与中间值的位置关系。
   1.当nums[mid] > nums.back()时，说明mid此时一定在第一个数组中，因为nums[mid]比第二个数组的最大值都更大，不可能落在第二个数组中，此时数组的最小元素一定在mid的右边，此时我们更新搜索区间的左边界，left = mid + 1
   2.当nums[mid] <= nums.back()时，说明mid此时一定在第二个数组中，因为nums.back()比第一个数组的任意元素都更小，而nums[mid]比nums.back()还小，不可能落在第一个数组，此时数组的最小元素一定在mid的左边，此时我们更新搜索区间的右边界，right = mid
   我们使用一个while循环来寻找最小元素的位置，由于我们采用的是左闭右开的查找方式，因此区间合法的条件是left < right，当循环结束后left == right，此时nums[left]或者nums[right]都是最小值。
   有了这道题的基础以后，再回到最开始的题目：33. 搜索旋转排序数组。这道题我们可以直接利用上一题的函数，返回nums数组最小值的下标min_index，然后根据target与nums[min_index]的大小关系执行不同的初始化操作：
   1.如果target < nums[min_index]，这种情况就不需要进行二分查找了，一定找不到，直接返回-1
   2.如果上一个情况不满足的话，则说明target有可能在nums中，我们进行进一步的判断：
   （1）如果target > nums.back()，说明target一定在第一个子数组中，此时left = 0, right = min_index
   （2）如果target < nums.back()，说明nums可能被分割为两个有序数组，也可能依然保持整体有序，由于min_index一定是数组最小元素的下标，target一定在min_index的右边，无论是哪种情况都是成立的，此时left = min_index, right = nums.size() - 1，然后我们再进行一次二分查找即可，当我们查找到target时直接返回其下标，否则循环会正常退出，此时我们返回-1即可。

//153. 寻找旋转排序数组中的最小值
class Solution {
public:int findMin(vector<int>& nums){int left = 0, right = nums.size() - 1;   //使用左闭右开的搜索方式[left, right)int mid;while(left < right){mid = (left + right) / 2;if(nums[mid] > nums.back())  //数组最小值在mid的右边left = mid + 1;else right = mid;}return left;}int search(vector<int>& nums, int target) {int min_index = findMin(nums);   //先找出数组中最小元素下标if(target < nums[min_index]) return -1;  //超出范围，直接返回-1int left = target > nums.back() ? 0 : min_index;int right = target > nums.back() ? min_index : nums.size();int mid;while(left < right){mid = (left + right) / 2;if(nums[mid] > target)  right = mid;else if(nums[mid] < target)left = mid + 1;else return mid;}return -1;}
};