leetcode hot100#33. 搜索旋转排序数组(有条件的二分搜索)

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

问题： 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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

题解：

从算法复杂度要求就能看出来本题要求用二分搜索的方式结题，但是题中的数组不是有序的，和传统二分不同，所以本题不再根据mid元素和target的大小来决定进入哪个分支

观察可知，二分当前数组必有一个部分是有效的（有序的） 例如：

nums = [6,7,0,1,2,3,4,5] 一部分是6,7的，二部分是0,1,2,3,4,5 二分当前数组： 左块是一部分+二部分{6,7,0,1}，右块是二部分{2,3,4,5} 定义当前块只由一个部分构成，称之为有效块 所以右块是有效块（有序）

这样就可以分两种情况，先进入有效块的分支 如果我们要找的target不在有效块，就进入另一块

简单画个图：

yes no yes no 二分当前数组 右块有效 左块有效 target在有效块内 target在有效块内 进入左块进行二分 进入右块进行二分 进入右块进行二分 进入左块进行二分 class Solution { public: int search(vector<int>& nums, int target) { int left=0,right=nums.size()-1; int mid=0; if(nums.size()==0)return -1; while(left<=right){ mid=(left+right)/2; if(nums[mid]==target)return mid; if(nums[0]<=nums[mid]){//左块有效 if(nums[0]<=target&&nums[mid]>target){//target在左块内 right=mid-1; }else {//否则就进入右块 left=mid+1; } }else {//右块有效 if(nums[nums.size()-1]>=target&&nums[mid]<target){//target在右块内 left=mid+1; }else {//否则就进入左块 right=mid-1; } } } return -1; } };