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

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

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

输入: nums = [2，5，6，0，0，1，2],    target = 0输出: true

示例 2:

输入: nums = [2，5，6，0，0，1，2],     target = 3输出: false 解答：本题的实质就是在一个旋转后的升序数组中快速寻找目标值。对于小样本可以顺序比较，但对于大样本（百万级）就不可以这样做了，这才是这道题的目的所在。本题采用中值查找法。 我在这里做了如下的梳理：【1】中点在旋转点的左侧；中点在旋转点的右侧；【2】目标点的值大于中点；目标点小于中点。综合起来总共是四种情况，为此我们可以得到如下逻辑： 【1】中点在旋转点左侧且目标点大于中值点，那么取left = mid +1, right 不变； 【2】中点在旋转点左侧且目标点小于中值点，若 nums[right] < target, 那么取 right = mid - 1;否则取left = mid +1 ; 【3】中点在旋转点右侧且目标点大于中值点，若 nums[right] < target, 那么取 right = mid - 1;否则取left = mid +1 ; 【4】中点在旋转点右侧且目标点小于中值点，那么取right = mid -11, left不变; 以上可以精简为三点： 【1】 nums[mid] < nums[right] 【2】 nums[mid] > nums[right] 【3】 right-- （用于处理常数如 2 2 2 2 2 3 1 1 1   target = 3）

//81bool search2(vector
     
      & nums, int target){    if(nums.empty()) return false;    int left=0,right=nums.size()-1;    while(left
      
       = target) left=mid+1;            else right=mid-1;        }        else if(nums[mid]> nums[right])        {            if(nums[mid]> target && nums[left] <= target) right=mid-1;            else left=mid+1;        }        else right--;//在常数情况下如2，2，2，2，2，3, 1，1，1    target=3    }    return nums[left]==target;}//81