81 搜索旋转排序数组2.md

81、搜索旋转排序数组2

题目：

假设按照升序排列的数组在预先未知的某个点上进行了旋转。（例如，数组[0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2]）。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回true，否则返回false。

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

解法（二分查找法）：

二分查找套二分查找法，这道题与33不含重复元素的搜索旋转数组基本一样。解决办法是当nums[mid]==nums[start]相等的时候，start++，并且进入下一轮的循环。

	public boolean search(int[] nums, int target) {

		if (nums == null || nums.length == 0) {
			return false;
		}

		int start = 0;
		int end = nums.length - 1;
		int mid;

		while (start <= end) {
			mid = start + (end - start) / 2;

			if (nums[mid] == target)
				return true;

			// 跳过重复的值（关键所在）
			if (nums[start] == nums[mid]) {
				start++;
				continue;
			}

			// mid位于左半段
			if (nums[start] < nums[mid]) {
				// 注意等号，覆盖所有的搜索区间
				if (target < nums[mid] && nums[start] <= target) {
					end = mid - 1;
				} else {
					start = mid + 1;
				}
			}
			// mid位于右半段
			else {
				// 注意等号，覆盖所有的搜索区间
				if (nums[mid] < target && target <= nums[end]) {
					start = mid + 1;
				} else {
					end = mid - 1;
				}
			}
		}

		return false;

	}