[LeetCode] 033. Search in Rotated Sorted Array (Hard) (C++)

浏览数：248 / 时间：2015年06月08日

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)
Github: https://github.com/illuz/leetcode

033. Search in Rotated Sorted Array (Hard)

链接：

题目：https://leetcode.com/problems/search-in-rotated-sorted-array/
代码(github)：https://github.com/illuz/leetcode

题意：

在一个旋转过的有序数组中找一个数。
比如 4 5 6 7 0 1 2 就是一个“旋转过的有序数组”。

分析：

这是单纯二分搜索的变形。
因为旋转过不好定位，所以在找的时候可以先判断一下一个区间是完全有序的还是已经旋转过的，然后分类讨论。

代码：

C++:

class Solution {
public:
	int search(int A[], int n, int target) {
		int left = 0, right = n;
		while (left != right) {
			int mid = (left + right) / 2;
			if (A[mid] == target)
				return mid;
			if (A[mid] >= A[left]) {
				// [left~mid] is unrotated sorted
				if (A[left] <= target && target < A[mid])
					right = mid;
				else
					left = mid + 1;
			} else {
				// [mid~right] is unrotated sorted
				if (A[mid] < target && target <= A[right - 1])
					left = mid + 1;
				else
					right = mid;
			}
		}
		return -1;
	}
};

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

[LeetCode] 033. Search in Rotated Sorted Array (Hard) (C++)