7

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

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

int binary_search(std::vector<int> 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;
}
2
  • Правильно написать бинарный поиск — сложная задача. Даже Дональд Кнут (знаете?) в своей книге говорит, что почти все (в том числе он сам) с первой попытки пишут неправильно. Вот вам статья по теме.
    – VladD
    19 фев 2016 в 22:53
  • Точно. Я тоже не с первой попытки написал несколько обобщенных функций (типа man 3 bsearch) bsearcher, bsearch_lb, bsearch_ub на Си. (отличие от стандартной bsearch см. в комментариях по ссылке)
    – avp
    24 фев 2016 в 11:07

2 ответа 2

8

В вашей реализации неверно отрабатывал вариант, когда вы в качестве 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<int>& 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);
}
11
  • @VladD Угу, я там промежуточный вариант зря выложил) 19 фев 2016 в 23:12
  • Пока я писал тот комментарий, вы исправили код :)
    – VladD
    19 фев 2016 в 23:14
  • А ещё код ТС не взлетит из-за проверки A[0] после цикла. Пример: A = {0, 1, 2}, x = 2.
    – VladD
    19 фев 2016 в 23:15
  • 1
    И правда :) Буду копать дальше, очень уж мне не нравится использование A[0], а не A[l]. // Хотя, это проверка выхода за левую границу, может он и прав тут.
    – VladD
    19 фев 2016 в 23:32
  • 1
    @VladD Я тут, все-таки, подумал: а ведь и правда передаются граничные индексы left и right, а сравнение идет с A[0] - косяк, что-то как-то сразу в глаза не бросилось :) 20 фев 2016 в 0:17
8

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

Пример:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> 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;
}

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

3
  • Я так понял, что ему принципиально написать реализацию самому (ну, задача из учебного заведения, наверное), а не воспользоваться готовым решением, хотя, по факту мне стоило бы у него уточнить. 19 фев 2016 в 22:45
  • @StateItPrimitive: Тогда пусть будет два решения: вручную и со стандартной функцией. Одно из них точно подойдёт, а другое пригодится будущим читателям.
    – VladD
    19 фев 2016 в 22:46
  • Тоже верно, вариант наверняка :) 19 фев 2016 в 22:47

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.