Настройка сравнения в bsearch ()

Question

У меня есть массив адресов, которые указывают на целые числа (эти целые числа сортируются в порядке возрастания). У них есть повторяющиеся значения. Пример: 1, 2, 2, 3, 3, 3, 3, 4, 4 ......

Я пытаюсь заполучить все значения, которые превышают определенное значение (ключ). В настоящее время пытаюсь реализовать это с помощью бинарного поиск по алгоритму -

void *bsearch(
 const void *key,
 const void *base,
 size_t num,
 size_t width,
 int ( __cdecl *compare ) ( const void *, const void *)
);

Я не могу достичь этого полностью, но для некоторых из них.

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

Answer 1

Как отметили Клатчко и GMan, функция STL дает вам именно то, что вы просите: std :: upper_bound .

Однако, если вам нужно придерживаться bsearch, простейшим решением может быть итерация вперед, пока вы не достигнете нового значения.

void* p = bsearch(key, base, num, width, compare);
while ((p != end) &&           // however you define the end of the array - 
                               // base + num, perhaps?
       (compare(key, p)==0)){  // while p points to an element matching the key

   ++p; // advance p
}

Если вы хотите получить первое p, соответствующее ключу, а не первое, которое больше, просто используйте --p вместо ++p.

Предпочитаете ли вы этот или повторный двоичный поиск, как предполагает Майкл, зависит от размера массива и ожидаемого количества повторений.

Теперь заголовок вашего вопроса относится к настройке функции сравнения, но, как я понимаю, вопрос, который вам здесь не поможет, - функция сравнения должна сравнивать любые два эквивалентных объекта как эквивалентные, поэтому нет смысла распознавать, какой из несколько эквивалентных объектов является первым / последним своего типа в массиве. Если у вас не было другой проблемы, в частности, касающейся функции сравнения?

Answer 2

Да, вы можете использовать бинарный поиск. Хитрость заключается в том, что вы делаете, когда находите элемент с данным ключом ... если ваши нижний и верхний индексы не совпадают, вам нужно продолжить бинарный поиск в левой части вашего интервала ... то есть вы должны двигаться верхняя граница - текущая средняя точка. Таким образом, когда ваш бинарный поиск завершится, вы найдете первый такой элемент. Затем просто переберите все остальное.

Answer 3

Вы должны посмотреть на std :: upper_bound

Например, чтобы найти адрес первого значения> 3:

const int data[] = { 1, 2, 2, 3, 3, 3, 3, 4, 4, ... };
size_t data_count = sizeof(data) / sizeof(*data);

const int *ptr = std::upper_bound(data, data + data_count, 3);

// ptr will now point to the address of the first 4

Связанная функция: std :: lower_bound .

Answer 4

Если у вас реализовано двоичное дерево поиска, у вас есть алгоритм обхода дерева , чтобы сделать это. Вы можете добраться до необходимого узла «верхняя граница» и просто пройти по порядку оттуда. Обход проще, чем многократный поиск в дереве, т. Е. Обход дерева из n узлов потребует максимум n операций, тогда как поиск n раз займет (n.log n) операций. .