首页 > 代码库 > Search in Rotated Sorted Array
Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
【二分思路】
分情况讨论，数组可能有以下三种情况：
来源网络：http://blog.csdn.net/ljiabin/article/details/40453607
然后，再看每一种情况中，target在左边还是在右边，其中第一种情况还可以直接判断target有可能不在数组范围内。
代码：
int search(int* nums, int numsSize, int target) { int low=0; int high=numsSize-1; if(low>high)return -1; while(low<=high){ int mid=(low+high)/2; if(nums[mid]==target)return mid; if(nums[low]<=nums[high]){ if(nums[mid]>target)high=mid-1; else low=mid+1; } else if(nums[low]<=nums[mid]){ if(target<nums[low]||target>nums[mid])low=mid+1; else high=mid-1; } else{ if(target<nums[mid]||target>=nums[low])high=mid-1; else low=mid+1; } } return -1; }
Search in Rotated Sorted Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。