有重复数值的旋转排序数组的搜索

超、凢脫俗 2023-10-04 22:26 6阅读 0赞

## 搜索旋转排序数组 II ##

### 题目 ###

已知存在一个按非降序排列的整数数组 `nums` ，数组中的值不必互不相同。

在传递给函数之前，`nums` 在预先未知的某个下标 `k`（`0 <= k < nums.length`）上进行了 **旋转** ，使数组变为 `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`（下标 **从 0 开始** 计数）。例如， `[0,1,2,4,4,4,5,6,6,7]` 在下标 `5` 处经旋转后可能变为 `[4,5,6,6,7,0,1,2,4,4]` 。

给你 **旋转后** 的数组 `nums` 和一个整数 `target` ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 `nums` 中存在这个目标值 `target` ，则返回 `true` ，否则返回 `false` 。

你必须尽可能减少整个操作步骤。

### 解析 ###

用二分查找。但是因为这个题目有一个条件是数组中的数字可重复，那么就会有下面两种情况：

111111101

110111111

这两种情况下，如果通过二分查找的方式判断时，mid的值和left的值以及和right的值均相等，所以就没法判断target导致是在左区间还是在右区间。因此，针对这种情况就需要特殊处理，否则无法使用二分查找。特殊处理的方法即可以left加1和right减1，这样逐步缩小区间，直到满足二分查找的能力，再进行log(n)的检索方式。

### 代码 ###

public boolean search(int[] nums, int target) {
        
            
            int l = 0;
            int r = nums.length - 1;
            while (l + 1 < r) {
        
                int mid = (l + r) / 2;
                if (nums[mid] == target) {
        
                    return true;
                  //这里很关键
                } else if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
        
                    l++;
                    r--;
                    continue;
                } else if ((nums[l] < nums[mid] && (target < nums[mid] && target >= nums[l]))
                || (nums[l] > nums[mid] && (target >= nums[l] || target < nums[mid]))) {
        
                    r = mid;
                } else {
        
                    l = mid;
                }
            }
            return nums[l] == target || nums[r] == target;
        }