Leetcode-33 Search in Rotated Sorted Array

发表于 | 分类于 | 次

Search in Rotated Sorted Array

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).

Example 1

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

Example 2

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

解题思路

二分法。旋转数组分为左右两个递增部分，且左边元素大于右边元素。若 nums[mid]==target，返回 mid。当 nums[mid] 在左边，即 nums[mid]>nums[r]，若 nums[l]<=target<nums[mid]，搜索左边，否则搜索右边。当 nums[mid] 在右边，即 nums[mid]<nums[l]，若 nums[mid]<target<=nums[r]，搜索右边，否则搜索左边。

复杂度分析

  • 时间复杂度：$O(logn)$。
  • 空间复杂度：$O(1)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
	int search(vector<int>& nums, int target) {
		if (nums.size() == 0) return -1;
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (nums[mid] == target) return mid;
			if (nums[mid] > nums[r]) { //mid在左边递增数组
				if (target >= nums[l] && target < nums[mid])
					r = mid - 1;
				else l = mid + 1;
			}
			else { //mid在右边递增数组
				if (target > nums[mid] && target <= nums[r])
					l = mid + 1;
				else r = mid - 1;
			}
		}
		return -1;
	}
};