с использованием двоичного поиска для подсчета вхождений

Question

Предположим, что я отсортировал массив A длиной n так 1 Мне нужно написать псевдокод программы, которая дает вывод всех вхождений каждого элемента.
Время выполнения алгоритма должно быть максимально k (c1 + c2 * log (n)).

пример - А = [1,1,2,2,2,5,5,5,5] ----> (1,2) (2,3) (5,4)

Я думал об использовании двоичного поиска, когда первый элемент, который я хочу сосчитать, - A [1], и мне нужно найти его последнее вхождение.
, то следующий элемент - это A [последний индекс появления + 1] и т. Д.

Мне немного сложно с идеей и записать его как псевдокод.

Тпх

Answer 1

рекурсивный алгоритм, он получает слева и справа позиции и вычисляет среднее положение. Идти глубже, если есть изменение числа, en edge. Здесь просто бинарный поиск. Но как только он обнаружит (на расстоянии = 1) ребро, изменение чисел, он вернет его в 4 значения: «какая последовательность чисел закончилась», «на какой позиции», «что началось», «на каком месте». Родительский узел затем объединяет эти 4 значения с левой и правой стороны, и если он обнаруживает полную последовательность «посередине», он сразу же печатает ее и передает только конечный край (слева) и начальный край (справа).

Answer 2

Невозможно достичь этой асимптотической сложности. Причина в том, какой алгоритм он имеет. Когда все n элементов различны, он должен вернуть все элементы. Это означает, что он должен их прочитать. Конечно, эта операция принимает O (n).

Answer 3

Вы можете рассчитывать количество вхождений для одной записи в O (журнал (п))

static int count(int[] array, int target, int start, int end, Func<int, int, bool> compare) 
    { 
     if (end < start) { return start; } 

     int m = (start + end)/2; 

     if (compare(target, array[m])) { return count(array, target, start, m - 1, compare); } 
     else { return count(array, target, m + 1, end, compare); } 
    } 


    static void Main(string[] args) 
    { 
     int[] a = { 1, 3, 8, 12, 12, 12, 25, 88 }; 
     int r1 = count(a, 12, 0, a.Length - 1, (x1, x2) => 
      { 
       return x1 < x2; 
      }); 

     int r2 = count(a, 12, 0, a.Length - 1, (x1, x2) => 
     { 
      return x1 <= x2; 
     }); 

     Console.Out.WriteLine("count=" + (r1 - r2).ToString()); 
    }