java - 在旋转排序数组中查找具有重复元素的元素

Question

此代码是问题的解决方案:https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

我在此处应用的逻辑非常适合在没有重复元素的旋转排序数组中查找元素。有人可以告诉我需要进行哪些修改才能使其适用于具有重复元素的数组吗？

[2,5,6,0,0,1,2], 目标 = 0 输出:真 [2,5,6,0,0,1,2], target = 3 输出: false

    public int search(int[] nums, int target) {
        if(nums.length== 0) return -1;

        int left= 0; int right= nums.length -1;

        // find the pivot element i.e, the one that breaks the sorted order of the array
        while(left< right){
            int mid= left+ (right- left)/ 2;
            // if mid< right that means this much part of the array is sorted
            // then do binary search on left and mid
            if(nums[mid]< nums[right])
                right= mid;
            // if mid> right that means this part of the array is not sorted
            // then do binary search on mid+1 to right
            else
                left= mid+ 1;
        }
        int pivot= left;
        int index= -1;
        // if target is between pivot till end then call binary search on that
        if(target>= nums[pivot] && target<= nums[nums.length- 1]){
            index= binarySearch(nums, target, pivot, nums.length- 1);
        }    
        // if target is between start and pivot then call binary search on that
        else{
            index= binarySearch(nums, target, 0, pivot -1);
        }  

        return index;
    }

    // binary search returning index of the mid element
    public int binarySearch(int[] nums, int target, int s, int e){
        while(s<= e){
            int mid= s + (e-s)/ 2;
            if(nums[mid]== target)
                return mid;
            else if(target> nums[mid])
                s= mid+ 1;
            else
                e= mid -1;
        }
        return -1;
    }

Answer 1

您的算法中的问题在于，当其值重复时，您不确定是否找到了准确的主元。 例如，对于数组 [8,9,2,2,4,5,6]，您的算法将第 4 个位置的元素作为主元(从 0 开始计数是元素 3)。 这样，数组的左侧部分将是未排序的 [8,9,2]，因此二进制搜索不起作用。

一个非常简单的解决方案是找到两个枢轴(我们称之为 left_pivot 和 right_pivot)。 right_pivot 正是您已经找到的那个，它被定义为“具有数组最低值的元素”。\ left_pivot 被定义为“具有数组最高值的元素”，您可以通过简单的修改找到:

       while(left< right){
            int mid= left+ (right- left)/ 2;
            if (mid * 2 < right)
                mid = mid + 1
            // if mid< right that means this much part of the array is sorted
            // then do binary search on left and mid
            if(nums[mid]< nums[right])
                right= mid-1;
            // if mid> right that means this part of the array is not sorted
            // then do binary search on mid+1 to right
            else
                left= mid;
        }

然后在数组的左侧部分进行二分查找，从索引 0 到索引 left_pivot(而不是 pivot-1)，在数组右侧从索引 right_pivot 到 length-1 进行二分查找