LeetCode Search in Rotated Sorted Array

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


这一题和LeetCode Find Minimum in Rotated Sorted Array类似,只不过不是查找最小值,而是查找某个target是否存在。也是采用二分查找的思路,首先判断nums[m]和nums[r]的关系,如果nums[m]<nums[r],说明右半部分是有序的,看看target是否在该部分范围内,如果在,则l=mid+1;否则r=mid-1。如果nums[m]>nums[r],说明右半部分无序,则左半部分有序,看看target是否在左半部分范围内,如果在,则r=mid-1;否则l=mid+1。如此循环下去。

完整代码如下:

class Solution {
public:
	int search(vector<int>& nums, int target) {
		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]) {
				if (target > nums[mid] && target <= nums[r]) {
					l = mid + 1;
				}
				else {
					r = mid - 1;
				}
			}
			else {
				if (target >= nums[l] && target < nums[mid]) {
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
			}
		}
		return -1;
	}
};

本代码提交AC,用时9MS。

One thought on “LeetCode Search in Rotated Sorted Array

  1. Pingback: LeetCode Search in Rotated Sorted Array II | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *