leetcode第33道，难度为medium，数组搜索问题，是二分查找的升级版。

Description

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:

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

来源：leetcode 33 search in rotated sorted array

Solution

Apporach 1 recursive

通过题目的要求，不难想到需要使用二分查找，只是在二分查找时，需要注意在数组中间会出现转折点。我的方法是使用递归，将数组分割成为多段，其中每段都是不具有拐点的。这样就能用常规的二分查找法进行搜索了。

int binarySearch(const vector<int>& nums, int target, int left, int right) {
    if (nums[left] <= nums[right]) { // ascend
	while (left <= right) {
	    int mid = (left+right) / 2;
	    if (nums[mid] < target) {
		left = mid + 1;
	    }
	    else if (nums[mid] > target) {
		right = mid - 1;
	    }
	    else {
		return mid;
	    }
	}
    }
    else { // descend
	while (left <= right) {
	    int mid = (left+right) / 2;
	    if (nums[mid] < target) {
		right = mid - 1;
	    }
	    else if (nums[mid] > target) {
		left = mid + 1;
	    }
	    else {
		return mid;
	    }
	}
    }
    return -1;
}

int searchHelper(const vector<int>& nums, int target, int left, int right) {
    int front = nums[left];
    int back = nums[right];
    int mid = nums[(left+right)/2];

    if ((front <= mid && mid <= back)
	|| (front >= mid && mid >= back)) {
	return binarySearch(nums, target, left, right);
    }

    int posMid = (left + right) / 2;

    int ans1 = searchHelper(nums, target, left, posMid);
    if (ans1 != -1) {
	return ans1;
    }

    int ans2 = searchHelper(nums, target, posMid, right);
    if (ans2 != -1) {
	return ans2;
    }
    return -1;
}

int search(vector<int>& nums, int target) {
    if (nums.empty()) {
	return -1;
    }

    return searchHelper(nums, target, 0, nums.size()-1);
}

我在解题的过程中，还是有些地方没有注意到：

  • 二分查找时，需要注意数组可能是升序或降序
  • 输入数组为空的边界条件

Approach 2

这种解法截取自solution sample中最快的那一档。直接在循环中查找求解，这样的解法简练很多。

int search(vector<int>& nums, int target) {
    if (nums.empty()) return -1;
    int low = 0, high = nums.size() - 1;
    while (low <= high) {
	int mid = (high - low)/2 + low;
	if (target == nums[mid]) return mid;
	if (nums[low] <= nums[mid]) {
	    if (nums[low] <= target and target <= nums[mid])
		high = mid - 1;
	    else low = mid + 1;
	}
	else {
	    if (nums[mid] <= target and target <= nums[high])
		low = mid + 1;
	    else high = mid - 1;
	}
    }
    return -1;
}

分析了这种解法后，我发现我漏掉了题目中的 ascending 条件。不过还是需要考虑 {3, 1} 这样的情况出现。