Бинарный поиск элементов samller

Question

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

Обратите внимание на все в комментариях, моя первая попытка, к которой я попытался приблизиться (удалите связанный список и поменяйте его местами с int)

Второй, он работал нормально, но никому не нравится спагетти-код, и это также спутало мою вторую попытку!

help: библиотечный подход или алгоритми c подход (предпочтительно)

PS: мой Engli sh ужасен c: p

Первая попытка:

Ввод: 1 4 6 7 8 8 8 11 30

вывод: [7, 6, 4, 1]

что я хочу вывод: [8,8,8,7, 6, 4, 1]

2 // подсчитать, сколько у нас дубликатов

public static   LinkedList<Integer> BinarySearch(int []arr ,int key) {

    LinkedList<Integer> ll=new LinkedList<>();

    int start=0;
    int end=arr.length-1;

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

        if (arr[mid]>key)end=mid-1;
        if (arr[mid]<key)start=mid+1;
        else {

            int key2=arr[mid];
            while(--mid>=0 && key2==key) {
                ll.add(arr[mid]); //return mid+1
            }
            return ll;
        }
    }
    return null;//return 0
}

Answer 1

Во-первых, у вас есть неприятная ошибка при проверке состояния:

if (arr[mid]>key)end=mid-1;
if (arr[mid]<key)start=mid+1;
else {

Три условия должны быть взаимоисключающими. В вашей версии они не. Это должно быть:

if (arr[mid]>key)end=mid-1;
else if (arr[mid]<key)start=mid+1;
else {

Что касается возврата и подсчета дубликатов ключей, когда в вашем массиве есть повторяющиеся значения, нет никаких гарантий, что ваш двоичный поиск попадет в самый правый экземпляр. Когда вы сопоставляете ключ, вы должны сначала перемещаться вправо в массиве до тех пор, пока у вас больше не будет совпадения, а затем перейти влево к началу массива, добавляя элементы и подсчитывая совпадения ключей.

if (arr[mid]>key) end=mid-1;
else if (arr[mid]<key) start=mid+1;
else {
    int right = mid+1;
    while(right < arr.length && arr[right] == key) 
        right++;

    int keyCount = 0;
    for(int i=right-1; i>=0; i--) {
        if(arr[i] == key) keyCount++;
        ll.add(arr[i]); 
    }
    System.out.format("Duplicates: %d%n", keyCount-1);
    return ll;
}

Test:

System.out.println(BinarySearch(new int[] {1,4,6,7,8,8,8,11,30}, 8));

Вывод:

Duplicates: 2
[8, 8, 8, 7, 6, 4, 1]