[LeetCode]Search in Rotated Sorted Array II

有duplicate的情况，duplicate造成的问题就是这个时候我们没办法区分那一边是sorted的。
对于递归的版本来说，我们就只能去两边一起找，只要一边有的话就返回true。Worst case：T(N) = 2 * T(N/2) + 1，根据Master Theorem, 时间复杂度是O(N)。

代码如下：

	public class Solution {
	public boolean search(int[] A, int target) {
	int len = A.length;
	int lo = 0;
	int hi = len - 1;
	return isFound(A, target, 0, len - 1);
	}
	private boolean isFound(int[] A, int target, int lo, int hi){
	if (lo > hi)
	return false;
	int mid = (lo + hi) / 2;
	if (A[mid] == target)
	return true;
	if (A[lo] < A[mid]){
	if (target >= A[lo] && target < A[mid])
	return isFound(A, target, lo, mid - 1);
	else
	return isFound(A, target, mid + 1, hi);
	} else if (A[lo] > A[mid]){
	if (target <= A[hi] && target > A[mid])
	return isFound(A, target, mid + 1, hi);
	else
	return isFound(A, target, lo, mid - 1);
	} else {
	if (A[mid] == target)
	return true;
	else
	return isFound(A, target, lo, mid - 1) || isFound(A, target, mid + 1, hi);
	}
	}
	}

view raw search rotated sorted array II recursive.java hosted with ❤ by GitHub

对于迭代的版本来说, 当我们没办法判断[mid,hi]区间是不是sorted的时候，我们只能排除hi位置的数字，所以只需要--hi即可，剩下的还是一样。最坏的情况也是O(N)。

代码如下：

	public class Solution {
	public int findMin(int[] num) {
	if (num == null)
	return -1;
	int len = num.length;
	int lo = 0, hi = len - 1;
	while (lo < hi) {
	int mid = lo + (hi - lo) / 2;
	if (num[mid] < num[hi])
	hi = mid;
	else if (num[mid] > num[hi])
	lo = mid + 1;
	else
	hi--;
	}
	return num[lo];
	}
	}

view raw find minimum in rotate sorted array ii iterative.java hosted with ❤ by GitHub