Поиск и диапазон поиска?

bsearch довольно хорош для прямого поиска, но что мне следует использовать, если мне нужен, например, диапазон поиска?

Обновить

например, если я хочу найти диапазон значений между a и b ( a >= x

Обновить

Диапазон значений может быть не равным. поэтому, если у меня есть массив (10,20,30), и я пытаюсь найти "15", я хочу получить адрес (указатель) на минимальный диапазон, который является ближайшим, в этом примере это диапазон (10,20)

Источник

2 ответа

Решение

Один из параметров bsearch take это количество элементов для поиска. Так что вместо, например, 100, сделайте поиск в 42 ...

bsearch("foo", data, /*100*/42, sizeof *data, cmpfx);

После обновления

Что бы я сделал, это ручной (то есть я бы написал код) бинарный поиск.

Идея состоит в том, чтобы сравнить средний элемент (оставшегося) массива с нижним и верхним пределом. Если он меньше, то нижний предел снова ищите в маленькой половине; если он больше верхнего предела, ищите снова в большой половине; в противном случае вы нашли элемент в диапазоне.

После 2-го обновления

Вы хотите вернуть пару указателей?

Вы должны обернуть их внутри структуры или передать адреса указателей в функции... или что-то в этом роде.

Но теперь у вас есть более простой поиск: ищите, пока не найдете значение (и не вернете диапазон длины 0), или пока не собираетесь потерпеть неудачу. Диапазон между значением массива, которое вы в последний раз просматривали, и, в зависимости от того, как именно вы попали в ситуацию сбоя, значением одной из сторон или ПУСТОЙ, если вы находитесь в конце массива.

Источник

bsearch() Функция предназначена для поиска одного элемента, соответствующего некоторому условию. Согласно справочной странице:

RETURN VALUE
       The bsearch() function returns a pointer to a matching  member  of  the
       array,  or  NULL  if no match is found.  If there are multiple elements
       that match the key, the element returned is unspecified.

Ключевым моментом здесь является то, что если есть несколько элементов, которые соответствуют ключу, возвращаемый элемент не указан. Таким образом, вы не знаете, является ли элемент, который вы получаете, первым, последним или где-то посередине диапазона.

Если вы можете изменить свои требования так, чтобы вы искали элементы в массиве между A и B, и вы можете гарантировать, что в массиве ровно один A и ровно один B, то вы можете сначала найти A, а затем выполнить поиск B.

start = bsearch(A, array, N, sizeof(*array), compare);
end = bsearch(B, array, N, sizeof(*array), compare);

Возможно, вам придется написать свою собственную функцию, чтобы сделать именно то, что вы хотите.

Источник
Другие вопросы по тегам