简单二分查找：搜索旋转排序数组
问题：
思路：二分查找（ 时间：O（log n））
二分查找只能用于有序序列，旋转后的序列不是有序序列，但是用二分查找中的mid将数组一分为二后，总有一半的数组是有序的 （可用反证法证明）。可以在这部分有序数组中使用二分查找
代码：
class Solution {
public:
int search(vector<int>& nums, int target) {
int n=nums.size();
if( n==0 )
return -1;
if( n==1 )
return target==nums[0]? 0:-1;
int left=0;
int right=n-1;
int mid;
while( left<=right )
{
mid=( left+right )/2;
if( target==nums[mid] )
return mid;
if( nums[left]<=nums[mid] )
{
if( target>=nums[left] && target<=nums[mid] )
{
right=mid-1;
}
else
{
left=mid+1;
}
}
else if( nums[mid]<=nums[right] )
{
if( target>=nums[mid] && target<=nums[right] )
{
left=mid+1;
}
else
{
right=mid-1;
}
}
}
return -1;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153768.html
