LeetCode: Search in Rotated Sorted Array II

题目

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

分析

这道题是Search in Rotated Sorted Array的变形,因为有重复元素的存在,之前的方法就不不能直接用了,比如在{1, 3, 1, 1, 1}中寻找3, 结果就会出错。

出错的原因在于因为重复元素的存在,A[m]==A[l]时就不能确定在中点的哪一边是有序的,那就不能砍掉一半的查找范围了。

解决的办法是将左边界向右移动,直至A[m]!=A[l],这样一来在最坏情况下时间复杂度会变为O(n)。

源码

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

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

参考

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

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

/** * 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); })();