LeetCode 33. 搜索旋转排序数组
原题链接
中等
作者:
bruce
,
2021-01-25 00:32:17
,
所有人可见
,
阅读 278
/**
* 方法 1,就是遍历一遍,但是时间复杂度O(n),就不写了,方法 2,使用二分,时间复杂度是O(logn)
* 使用两次二分查找就可以做出来,
* 第一个二分是来找到这个数组的端点,
* 第二个二分是在严格单调的区间端点内进行查找即可
*/
int search(vector<int> &nums, int t)
{
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (nums[mid] >= nums[0])
{
l = mid;
}
else
r = mid - 1;
}
// 确定目标数所在的区间的边界
if (t >= nums[0]) // 如果目标数大于nums[0],说明在第一段
l = 0;
else
l = l + 1, r = nums.size() - 1; // 这里要注意如果只有1个数的话,那么不进行第一个二分,所以l= 1, r =0,最后的二分要取r端点,否则越界
while (l < r)
{
int mid = (l + r) >> 1;
if (nums[mid] >= t)
r = mid;
else
l = mid + 1;
}
return nums[r] == t ? l : -1; // nums要取右端点,否则越界
}