Найти элемент в Rotated Sorted Array с повторяющимися элементами

Question

Этот код является решением проблемы: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

Логика, которую я здесь применил, прекрасно работает для поиска элемента в повернутом отсортированном массиве без повторяющихся элементов. Может кто-нибудь сказать мне, какие изменения необходимы, чтобы он работал для массива с дублирующимися элементами?

[2,5,6,0,0,1,2], target = 0 output: true [2,5,6,0,0,1,2], target = 3 output: 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] ваш алгоритм находит как pivot элемент в 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