搜索旋转排序数组Ⅱ（二分法实现）

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

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

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

注意点

参考：搜索旋转排序数组（二分法实现） 1、有序数组经过旋转后会变为部分有序的数组； 2、我们使用二分法后会出现三种情况如下：

情况一：无法判断左右区间哪个是有序区间，这种情况我们只能排除一个节点的元素，无法进行区间选择；（如101111这种情况，则当nums[left] == nums[mid] == nums[right时]）情况二：左区间为有序区间，则判断目标节点是否在有序区间中（左区间），在，则选取左区间；否则，选取右区间；情况二：右区间为有序区间，则判断目标节点是否在有序区间中（右区间），在，则选取右区间；否则，选取左区间。

实现

public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) return false; int left = 0; //左指针 int right = nums.length - 1; //右指针 while (left <= right){ int mid = left + (right - left) / 2; //中间指针 //如果中间值为目标值，直接返回 if (nums[mid] == target) return true; //无法判断左边[left，mid）是否为有序区间 if (nums[left] == nums[mid]){ //只排除一个元素 left ++; //左边[left，mid）为有序区间 }else if (nums[left] < nums[mid]){ //目标值在左顺序区间中 if (target >= nums[left] && target < nums[mid]){ //取左区间 right = mid - 1; }else { //否则，取右区间 left = mid + 1; } //左边[left，mid）为无序区间（则右区间为有序区间） }else { //目标值在右顺序区间中 if(target > nums[mid] && target <= nums[right]){ //取右区间 left = mid + 1; }else { //否则，取左区间 right = mid - 1; } } } return false; }