Реализация bsearch

192
29 мая 2018, 18:40

Хочу ускорить программу встраивая bsearch, т.к. не первый раз делаю bsearch. Задача такая - есть массив чисел. Есть длинна массива. Есть искомое число. Нужно получить номер в массиве, если такого нету - то ближайшее слева или справа. Я приведу свой вариант, но... возможно есть вариант получше.

int q = 0;
  int i,L,R;
  int window_sizes[] = {0,4,8,12,16,64,128,256,512,1024,4096,8192,16384 };
  R = sizeof(window_sizes)/sizeof(window_sizes[0]);
  while (L < R) {
     i = L+ ((R-L)>>1);//Середина диапазона
     if ( window_sizes[i] > q)  R = i;  // Переходим влево
       else {
       if (window_sizes[i] == q) break;
       L = i; // Переходим вправо
       }          
       }

В итоге хочу создать макрос и использовать его везде.

Напомню.. bsearch - двоичный поиск. Метод поиска в упорядоченом массиве с названием поиск методом половинного деления. Т.е. (коротко) сравниваем искомое с числом посередине диапазона, если меньше - переходим к сравнению в левом диапазоне (с тем которое посередине левого диапазона), иначе справа... и так далее. В отличии от линейного поиска - сокращает среднее время поиска во много раз.

READ ALSO
C++ Передача значений из файла в массив

C++ Передача значений из файла в массив

Хочу брать из файла числа и вписывать в элементы массиваПочему не работает? И как работает while (file >> k), while (file >> m), если я правильно написал...

186
Пользовательский класс string

Пользовательский класс string

Зависает программа после ввода строкиПодскажите в чем ошибка?

205
Процесс ест 50% ЦП- C++

Процесс ест 50% ЦП- C++

Как можно упростить/улучшить код, чтобы он не кушал ~50% ЦП? Вот, собственно, код:

177
Неизвестная проблема с boost::process C++

Неизвестная проблема с boost::process C++

возникла проблема с использованием boost, использую пример по туториалу с двуноправленным контейнером, но он почему-то отказывается работать

174