旋转数组查找
给定一个排序数组nums(nums中有无重复元素)，且nums可能以某个未知下 标旋转，给定目标值target，求target是否在nums中出现，若出现返回所在下标 ，未出现返回-1。 LeetCode 33. Search in Rotated Sorted Array
在旋转数组[7, 9, 12, 15, 20, 1, 3, 6]中，若硬使用未加修改的二分查找 ，查找target = 12 或target = 3，会出现什么情况? 当前mid = 3，nums[mid] = 15: 查找target = 12 : target(12) < nums[mid] (15)，则在子区间[7, 9, 12]中继续查找，可找到12，返回 正确结果。 查找target = 3 : target(3) < nums[mid] (15)，则在子区间[7, 9, 12]中继续查找，不可找到3，返回错误结果。 依旧 分三种情况讨论，target<nums[mid];target > nums[mid];taregt>nums[mid];
class Solution{
public:
int search(std::vector<int> &nums,int target){
int begin = 0;
int end = nums.size()-1;
while(begin <= end){
int mid = (begin + end)/2;
if(target == nums[mid]){
return mid;
}
else if(target <nums[mid]){
if(nums[begin] > nums[mid]){
if(target > nums[begin]){
end = mid -1;
}
else{
begin = mid+1;
}
}
else if(nums[begin > nums[mid]){
end = mid -1;
}
else if(nums[begin] == nums[mid]){
begin = mid + 1;
}
}
else if(target > nums[mid]){
if(nums[begin] < nums[mid]){
begin = mid +1;
}
else if(nums[begin] > nums[mid]){
if(target >= nusm[begin]){
end = mid -1;
}
else{
begin = mid +1;
}
}
else if(nums[begin] = nums[mid]){
begin = mid +1;
}
}
}
return -1;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018.04.06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
