[LeetCode]33. Search in Rotated Sorted Array


title: [LeetCode]33. Search in Rotated Sorted Array tags: binary-search

notebook: LeetCode

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [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.

Your algorithm’s runtime complexity must be in the order of O(log n).

1
2
3
4
5
6
7
8
Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

给定一个升序数组, 在某个pivot位置发生了颠倒, 同时给定一个target, 在数组中查找确定这个target是否在这个数组中. 如果在, 返回它的下标index, 如果不在,返回-1.

假设数组中不存在重复元素.

要求时间复杂度为O(logn).

Solution

Analysis

从背景题意中,可以看出数组可以看做是一个有序数组的变形, 一个数组分为两个有序的子数组: 左边一部分和右边一部分. 同时左右两个小数组都是有序的. 同时根据题目关于时间复杂度的要求,可以看出,真正的解决方法应该是使用二分查找法.

但是这里不能直接使用二分查找法,因为整个数组并不是有序的, 所以需要对二分查找做一个变形. 确保查找,变换的范围的数字是有序的. 之后就可以使用二分查找了.

这里就根据nums[mid] 和 nums[right]之间的大小关系确定子数组[mid, right]是否是有序的:

  • 如果nums[mid] < nums[right]: 那么说明[mid, right]是有序的, 之前判断nums[mid]和查找数字target之间的对等关系, 相等直接返回结果; 不相等,执行到这里后, 在[mid, right]子数组范围内, 我们在判断target所坐落的范围. 在[mid, right]这个子数组范围内, 如果target在这个范围内, 那么我们修改left指针的值, 否则修改right指针的值.
  • 否则, 说明[left, mid]这个子范围是有序的, 同样,我们判断target是否在这个区间内, 如果在, 变化right指针, 如果不在,变化left指针.

有一点需要注意的是, 这里先判断了nums[mid]和nums[right]的大小关系, 而不是nums[mid]和nums[left]的大小关系, 如果先判断后者的话, nums[left] < nums[mid],变换left指针后, 容易出错. 本质在于, int运算的除法的取整性. left有可能等于mid. 加入target正好在left位置处, 而right=left+1, 那么mid=left, 这样变化后,找到target, 返回错误结果.

具体代码如下:

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;

while (left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
// 如果target就在left处, 这样left变为mid+1, 导致出错.
else if (nums[mid] < nums[right]){// 先检测后半段;因为有可能mid==left
if (nums[mid] < target && nums[right] >= target)
left = mid + 1;
else
right = mid -1;
}
else {
if (nums[left] <= target && nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
}
return -1;
}
};
您的支持就是我更新的最大动力!谢谢!