Как найти количество вхождений числа в отсортированном массиве в O (logn)

Question

У меня есть отсортированный массив целых чисел. По заданному числу, как найти число вхождений этого числа в O (logn) даже в худшем случае.

Answer 1

Выполните один двоичный поиск точки, в которой все элементы слева меньше вашего числа, а все справа равны или больше, а один - в точке, где все элементы меньше или равны слева и больше справа. ,

Другими словами: в одном поиске ваш «тест» равен <, а в другом поиске - <=.

Оба поиска log n, так что это ваш итог.

Например, в C ++ вам понадобятся две функции: std::lower_bound и std::upper_bound - кажется, что существующие функции бинарного поиска Java (в коллекциях) всегда пытаются найти конкретное значение, так что вы, вероятно, имеете выполнить поиск самостоятельно, если вы используете это.

Важно, чтобы вы использовали вариант двоичного поиска, который использует только двоичный предикат! Если вы используете вариант, который проверяет, попал ли он по определенной клавише «случайно», он иногда слишком быстро завершается для этой конкретной задачи.

Answer 2

Двоичный поиск номера, затем двоичный поиск начала и конца цикла.

Answer 3

Поиск точек вставки number + 0.5 и number - 0.5 с использованием двух двоичных поисков.Количество элементов со значением number в списке - это разность позиций (индексов) этих двух точек вставки.

Answer 4

Запустите функцию ниже один раз, как есть, и один раз с условием if, измененным на if (a [mid] <= val) и соответствующие изменения в рекурсивных вызовах.Два возвращаемых значения являются начальным и конечным вхождением конкретного значения. </p>

      int  binmin(int a[], int start, int end,int val )
        {
         if(start<end)
            {
            int mid = (start+end)/2;
            if(a[mid]>=val)
            {
                binmin(a,start,mid-1,val);
            }
            else if(a[mid]<val)
            {
                binmin(a,mid+1,end,val);
            }

    }
    else if(start>end)
            return start;



  }