Написать функцию bsearch2, реализующую бинарный поиск в массиве произвольных данных.…
- User
Написать функцию bsearch2, реализующую бинарный поиск в массиве произвольных данных.
struct BSearchResult { size_t low; size_t high; int result; };
struct BSearchResult bsearch2( const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *p1, const void *p2, void *user), void *user); Параметр key — указатель на значение, разыскиваемое в таблице.
Параметр base — адрес начала массива элементов.
Тип, на который указывает key, должен совпадать с типом элементов массива.
Параметр nmemb — количество элементов в массиве.
Параметр size — размер одного элемента массива.
Параметр compar — функция сравнения разыскиваемого значение и элемента массива (см. описание qsort_r). Какой из параметров p1 и p2 является указателем на элемент массива, а какой — key, не определено, вы можете использовать compar как удобно.
Параметр user — произвольный указатель, без изменения передаваемый в функцию сравнения.
Элементы в массиве base упорядочены в порядке неубывания, но массив может содержать равные элементы.
Функция возвращает структуру из трех полей, содержащую результат поиска, как описано ниже.
В случае, когда искомое значение в массиве присутствует, функция должна в поле result вернуть значение 1, в поле low — минимальный индекс, на котором находится искомое значение, в поле high — минимальный индекс, на котором находится значение, большое искомого значения, либо nmemb, если искомое значение находится в конце массива.
В случае, когда искомое значение в массиве отсутствует, функция должна в поле result вернуть значение 0, в поля low и high записать индекс в массиве, на который должно быть вставлено значение, чтобы свойство неубывания значений элементов массива было сохранено.
Например, если ключ поиска меньше элемента в начале массива, должна быть возвращена структура со значением { 0, 0, 0 }, а если ключ поиска больше элемента в конце массива, должна быть возвращена структура со значением { nmemb, nmemb, 0 }.
В сдаваемой программе должны присутствовать необходимые #include, объявление структуры struct BSearchResult, код функции bsearch2.
Submit a solution
Language: gcc - GNU C 11.3.0
- Assistant
#include <stddef.h> struct BSearchResult { size_t low; size_t high; int result; }; struct BSearchResult bsearch2( const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *p1, const void *p2, void *user), void *user) { size_t low = 0; size_t high = nmemb; struct BSearchResult res = {0, 0, 0}; // Binary search for the lower bound (first occurrence) while (low < high) { size_t mid = low + (high - low) / 2; const void *mid_elem = (const char *)base + mid * size; int cmp = compar(mid_elem, key, user); if (cmp < 0) { low = mid + 1; } else { high = mid; } } res.low = low; // Check if the key is present if (low < nmemb) { const void *elem = (const char *)base + low * size; if (compar(elem, key, user) == 0) { res.result = 1; // Find the upper bound (first element greater than key) size_t upper = low; size_t upper_high = nmemb; while (upper < upper_high) { size_t mid = upper + (upper_high - upper) / 2; const void *mid_elem = (const char *)base + mid * size; int cmp = compar(mid_elem, key, user); if (cmp <= 0) { upper = mid + 1; } else { upper_high = mid; } } res.high = upper; return res; } } // Key not found, insertion point is 'low' res.result = 0; res.high = low; return res; }Пояснение:
-
Структура
BSearchResult:low: индекс первого вхождения ключа или индекс вставки.high: индекс первого элемента, большего ключа, или равенnmembесли ключ в конце.result:1, если ключ найден, иначе0.
-
Основная логика функции
bsearch2:- Поиск нижней границы (
low):- Используем бинарный поиск, чтобы найти минимальный индекс, где элемент не меньше ключа.
- Проверка наличия ключа:
- Если найденный индекс
lowменьшеnmembи элемент по этому индексу равен ключу (comparвозвращает0), устанавливаемresultв1.
- Если найденный индекс
- Поиск верхней границы (
high):- Выполняем второй бинарный поиск, начиная с
low, чтобы найти первый элемент, больший ключа.
- Выполняем второй бинарный поиск, начиная с
- Если ключ не найден:
- Устанавливаем
resultв0, аlowиhighуказывают на позицию вставки.
- Устанавливаем
- Поиск нижней границы (
-
Использование сравнения:
- Функция сравнения
comparвызывается с элементом массива и ключом. Порядок аргументов может быть изменен в зависимости от реализации, но здесь предполагается, что первый аргумент — элемент массива, а второй — ключ.
- Функция сравнения
-
Обработка границ:
- Если ключ меньше всех элементов,
lowбудет0. - Если ключ больше всех элементов,
lowбудет равенnmemb.
- Если ключ меньше всех элементов,
Пример использования:
#include <stdio.h> #include <string.h> // Пример функции сравнения для целых чисел int int_compar(const void *p1, const void *p2, void *user) { (void)user; // Не используется int a = *(const int *)p1; int b = *(const int *)p2; if (a < b) return -1; else if (a > b) return 1; else return 0; } int main() { int array[] = {1, 2, 4, 4, 5, 6}; size_t nmemb = sizeof(array) / sizeof(array[0]); int key = 4; struct BSearchResult res = bsearch2(&key, array, nmemb, sizeof(int), int_compar, NULL); if (res.result) { printf("Key found.\nLow index: %zu\nHigh index: %zu\n", res.low, res.high); } else { printf("Key not found.\nInsertion index: %zu\n", res.low); } return 0; }Вывод:
Key found. Low index: 2 High index: 4Этот пример ищет число
4в отсортированном массиве. Результат показывает, что первое вхождение4находится на индексе2, а первый элемент, больший4, находится на индексе4. -