LeetCode热题100 搜索旋转排序数组

题目描述整数数组 nums 按升序排列数组中的值 互不相同 。在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 向左旋转使数组变为 [nums[k], nums[k1], …, 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) 的算法解决此问题。示例 1输入nums [4,5,6,7,0,1,2], target 0输出4示例 2输入nums [4,5,6,7,0,1,2], target 3输出-1示例 3输入nums [1], target 0输出-1提示1 nums.length 5000−104nums[i]104-10^4 nums[i] 10^4−104nums[i]104nums 中的每个值都 独一无二题目数据保证 nums 在预先未知的某个下标上进行了旋转−104target104-10^4 target 10^4−104target104思路1 进行二分查找[l,mid] 和 [mid 1, r]中一定有一段是递增的我们判断递增那一份部分。2 如果递增那部分的范围中有target答案在这部分否则在另外一部分。代码classSolution{public:intsearch(vectorintnums,inttarget){intl0,rnums.size()-1;while(lr){intmidlr1;// 左边有序的部分if(nums[mid]nums[l]){// 答案在左边if(nums[l]targettargetnums[mid]){rmid;}// 答案在右边else{lmid1;}}// 右边有序else{// 答案在右边if(nums[mid1]targettargetnums[r]){lmid1;}// 答案在左边else{rmid;}}}// 找到返回l或rif(nums[l]target){returnl;}// 没找到返回-1else{return-1;}}};