LeetCode: Search in Rotated Sorted Array

题目

https://oj.leetcode.com/problems/search-in-rotated-sorted-array/

分析

还是运用二分的思想, 每次循环判断target在中点的左侧还是右侧,每次砍掉一半的查找范围, 直到得到最终结果。

在这个过程中用到的一个重要规律是: 

一个数字序列经过rotate之后, 以中间那个数字为边界, 一定一边是有序序列, 一边是 rotated有序序列(证明略)。

如何判断哪边是有序的呢? 如果中点大于左边界, 则左侧是有序序列, 否则右侧是有序序列。

分别用 l代表左边界, r代表右边界, m代表中间那个数,

如果A[m] == target, 则直接返回m即可。

如果A[m] >= A[l] ,说明左侧是有序序列

       如果target在左侧有序序列范围内, 则把 左边界l 设为 m+1

       否则target在右侧序列中, 则把 右边界r 设为 m-1

否则, 右侧是有序序列

       如果target在右侧有序序列范围内, 则把 左边界l 设为 m+1

       否则target在左侧有序序列范围内, 则把 右边界r 设为 m-1

 

P.S. 标准二分查找代码可以查看这里

代码

class Solution
{
public:
	int search(int A[], int n, int target)
	{
		if (n <= 0)
			return -1;
		int l = 0;
		int r = n - 1;
		int m;

		while (l <= r)
		{
			m = (l + r) / 2;
			if (A[m] == target)
				return m;
			else if (A[l] < A[m])
			{
				if (A[l] <= target && target <= A[m-1])
					r = m - 1;
				else
					l = m + 1;
			}
			else
			{
				if (A[m+1] <= target && target <= A[r])
					l = m + 1;
				else
					r = m - 1;
			}
		}
		return -1;
	}
};

参考

http://blog.csdn.net/linhuanmars/article/details/20525681

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39860279

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();