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

Question

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

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

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

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

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

Answer 1

Вы должны смотреть на 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 2

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

Answer 3

Как отметил Клацко и 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.

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

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

Answer 4

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