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;
	}
};