Найти количество элементов массива, меньших заданного

#cpp #алгоритм

Надо было найти количество элементов массива, меньших заданного в отсортированном
массиве без повторений. Причем сделать это надо максимально быстро. Я использовал бинпоиск,
вот что у меня вышло.

Почему-то работает не всегда. В чем может быть проблема?

int binary_search(std::vector A, int x, int left, int right)
{
   while (right - left > 1)
   {
      int mid = (left + right) / 2;
      if (A[mid] < x)
      {
         left = mid;
      }
      else
      {
         right = mid;
      }
   }
   if (x <= A[0])
   {
      return 0;
   }
   return left + 1;
}

    

Ответы

Ответ 1

В вашей реализации неверно отрабатывал вариант, когда вы в качестве x передаете переменную,
значение которой больше любого элемента массива (правда на самом деле у вас vector,
а не массив, но не суть), а также в конце вы сравниваете с A[0], а не с A[left], хотя
по логике вещей с ним бы и нужно сравнивать (ведь вы в границах диапазона решаете задачу,
по крайней мере судя по входным параметрам).

В вашем коде минимальными усилиями можно решить данную проблему если заменить вот
этот кусок:

if (x <= A[0])
{
    return 0;
}


на следующий:

if (x <= A[left])
   return 0;
else if (x > A[right])
   return (right - left + 1);


Кстати, будет эффективнее, если вы эту проверку переместите в начало процедуры, а
не в конец.

Ну и в начале неплохо бы проверять left и right на вхождение в границы диапазона
(ну и что left <= right), а то в итоге mid, через значение которого по индексу вы затем
обращаетесь, может выйти из них.

А еще экземпляр vector'а передавайте по ссылке с модификатором const (не вы же не
меняете объект внутри функции), чтобы в лишний раз не вызывать конструктор копирования.



Либо можно несколько поменять логику работы:

int binary_search(const std::vector& arr, int key, int left, int right)
{
   left = (left < 0) ? 0 : left;
   right = (right > arr.size() - 1) ? arr.size() - 1 : right;
   do
   {
      int middle = (left + right) / 2;

      if (key < arr[middle])
         right = middle - 1;
      else if (key > arr[middle])
         left = middle + 1;
      else
      {
         for (; (middle >= 0) && (key == arr[middle]); --middle){}
         return middle + 1;
      }

      if (left > right)
         return left;
   } while (true);
}


Ответ 2

Проще всего воспользоваться стандартным алгоритмом std::lower_bound, который возвращает
итератор на первый элемент, который не меньше данного.

Пример:

#include 
#include 
#include 

int main()
{
    std::vector v { 1, 2, 3, 3, 3, 3, 4, 4, 5 };
    const int pivot = 4;
    auto pos = std::lower_bound(std::begin(v), std::end(v), pivot);
    std::cout << std::distance(std::begin(v), pos);
    return 0;
}


Асимптотика алгоритма логарифмическая, т. к. он внутри реализует бинарный поиск.