leetcode题记 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

来源:力扣(LeetCode)

题解

这道题可以直接用二分法解决,但是这个二分法需要魔改左右边界迭代的判断。而这个魔改的思想,有点类似反证法。

在进行二分法的时候,数组的反转点或许在中点的左边或者右边,这让我们对数据位置的确定会产生一些困难。

这时候就需要换个思路,例如:
我们可以确定左边或者右边中的某一边是肯定按照顺序排列的,如果目标在这个按照顺序的个区间内,则将二分查找区域放到这边;
反之所有的情况都是在另一边,我们也将二分查找区域放到这另一边,这样不断进行下去,就会不断的无视这个翻转点进行二分查找了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < nums[right]) { // pivot in left
if (target > nums[mid] && target <= nums[right]) left = mid+1;
else right = mid-1;
} else { // pivot in right
if (target < nums[mid] && target >= nums[left]) right = mid-1;
else left = mid+1;
}
}
return -1;
}
};

结果

执行用时 : 4 ms, 在所有 C++ 提交中击败了92.20%的用户
内存消耗 : 8.5 MB, 在所有 C++ 提交中击败了98.16%的用户

Author: SmallXeon
Link: https://hexo.chensmallx.top/2019/08/01/leetcode-33-search/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
一些推广链接
几个便宜量大的小✈场: FASTLINK, YToo, 论坛邀请注册: ,
便宜量大但是稳定性不足的VPS: Virmach, 价格略贵但好用的VPN: , ,