Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Написать функцию bsearch2, реализующую бинарный поиск в массиве произвольных данных.…

  1. 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

  2. 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;
    }
    

    Пояснение:

    1. Структура BSearchResult:

      • low: индекс первого вхождения ключа или индекс вставки.
      • high: индекс первого элемента, большего ключа, или равен nmemb если ключ в конце.
      • result: 1, если ключ найден, иначе 0.
    2. Основная логика функции bsearch2:

      • Поиск нижней границы (low):
        • Используем бинарный поиск, чтобы найти минимальный индекс, где элемент не меньше ключа.
      • Проверка наличия ключа:
        • Если найденный индекс low меньше nmemb и элемент по этому индексу равен ключу (compar возвращает 0), устанавливаем result в 1.
      • Поиск верхней границы (high):
        • Выполняем второй бинарный поиск, начиная с low, чтобы найти первый элемент, больший ключа.
      • Если ключ не найден:
        • Устанавливаем result в 0, а low и high указывают на позицию вставки.
    3. Использование сравнения:

      • Функция сравнения compar вызывается с элементом массива и ключом. Порядок аргументов может быть изменен в зависимости от реализации, но здесь предполагается, что первый аргумент — элемент массива, а второй — ключ.
    4. Обработка границ:

      • Если ключ меньше всех элементов, 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.