LeetCode#33 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).

原题链接：https://leetcode.com/problems/search-in-rotated-sorted-array/

思路

使用start和end两个下标，从原来的数组上逐渐缩小搜索范围。
采用二分查找的思想，首先求出位于start和end的中间位置mid，比较nums[mid]与target的关系，如果相等则直接找到，否则分以下几种情况：

1. num[start]<=nums[mid]<=nums[end]，此时数组为有序数组，直接按照二分查找进行；
2. num[mid] >= num[start]，此时举例如序列{4,5,6,7,8,1,2,3}，nums[mid]位于左边的子递增序列上，由此引申出两种情况，一是target的值比nums[mid]小，比nums[start]大，则target位于左边[start,mid]的递增序列上，按照二分查找进行，二是target位于mid右方，以mid代替start，递归查找mid右边的子序列；
3. 同理，另一种情况是nums[mid]位于右边的子序列上，按照target可能的位置又可以分为二分查找或者递归执行。

代码

class Solution {
public:
	int search(vector<int>& nums, int target) {
		int len = nums.size();
		if (len == 0) {
			return -1;
		}
		return searchCore(nums, 0, len - 1 , target);
	}
	int searchCore(const vector<int>& nums, int start, int end, const int& target) {
		int mid = (start + end) / 2;
		if (nums[mid] == target) {
			return mid;
		}
		else if (start == end) {
			return -1;
		}
		else if (nums[start] <= nums[mid] && nums[mid] <= nums[end]) {
			return binarySearchCore(nums, start, end, target);
		}
		else if (nums[mid] >= nums[start]) {
			if (target >= nums[start] && target < nums[mid]) {
				return binarySearchCore(nums, start, mid - 1, target);
			}
			else {
				return searchCore(nums, mid + 1, end, target);
			}
		}
		else {
			if (target > nums[mid] && target <= nums[end]) {
				return binarySearchCore(nums, mid + 1, end, target);
			}
			else {
				return searchCore(nums, start, mid - 1, target);
			}
		}
		return -1;
	}
	int binarySearchCore(const vector<int>& nums, int start, int end, const int& target) {
		if (start > end) {
			return -1;
		}
		int mid = (start + end) / 2;
		if (nums[mid] == target) {
			return mid;
		}
		if (target < nums[mid]) {
			return binarySearchCore(nums, start, mid - 1, target);
		}
		else {
			return binarySearchCore(nums, mid + 1, end, target);
		}
		return -1;
	}
};