81. 搜索旋转排序数组

问题81 搜索旋转排序数组 ★★☆☆☆

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

这个题目和问题33几乎一样，差异点有两个：

1. 问题33里数组元素是distinct的，即没有重复值，而问题81里数组元素可能有重复值；
2. 问题33里rotation的位置是从第二个元素开始，即rotation后必然是两段，而问题81里rotation的位置可能是第一个元素，即rotation后可能和原数组是一样的。

因为上述差异点，问题81就比问题33难一些，尤其是当nums[mid]和nums[0]相等时，我们很难判断出当前哪个部分具备有序性。但是话说回来，当nums[mid] > nums[0]或者nums[mid] < nums[0]时，和问题33类似，我们可以判断出nums[left..mid]或者nums[mid..right]是不是有序的。而对于nums[mid] == nums[0]这种情况，最简单粗暴的做法就是同时更新left和right，然后继续下一层循环。

	public boolean search(int[] nums, int target) {
		int left = 0, right = nums.length-1;

		while (left <= right) {
			int mid = left + (right-left)/2;

			if (nums[left] == target
				|| nums[right] == target
				|| nums[mid] == target) {
				return true;
			}

			if (nums[mid] > nums[0]) {
				// num[left..mid] is no-decreasing sorted
				if (target > nums[left] && target < nums[mid]) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
			} else if (nums[mid] < nums[0]) {
				// num[mid..right] is non-decreasing sorted
				if (target > nums[mid] && target < nums[right]) {
					left = mid + 1;
				} else {
					right = mid - 1;
				}
			} else {
				left++;
				right--;
			}

		}

		return false;
	}

在 LeetCode 查看