Есть ли метод двоичного поиска в стандартной библиотеке C? - PullRequest
Новая
       39

Есть ли метод двоичного поиска в стандартной библиотеке C?

5 голосов
/ 10 июля 2019

Я не могу найти метод, реализующий бинарный поиск. Это потому, что мне не удалось его найти, или это потому, что его не существует?

Я думаю, что второй, но я не смог найти повторяющийся вопрос, так что, возможно, я ошибаюсь.

Ответы [ 2 ]

13 голосов
/ 10 июля 2019

Существует метод bsearch() в том же <stdlib.h>, как указано здесь , здесь и здесь .

Функция bsearch() использует алгоритм двоичного поиска, чтобы найти элемент, который соответствует ключу в отсортированном массиве из n элементов размера размера.(Тип size_t определен в <stdlib.h> как unsigned int.) Последний аргумент compare дает bsearch() указатель на функцию, которую он вызывает для сравнения ключа поиска с любым элементом массива.Эта функция должна возвращать значение, указывающее, является ли ее первый аргумент, ключ поиска, меньшим, равным или большим, чем ее второй аргумент, элементом массива для проверки.

Обычно следует использовать qsort() до bsearch(), поскольку массив должен быть отсортированным (должен быть в порядке возрастания, упорядочен по тем же критериям, что и compare) перед поиском.Этот шаг необходим, потому что алгоритм двоичного поиска проверяет, является ли ключ поиска выше или ниже среднего элемента в массиве, затем удаляет половину массива, проверяет середину результата, снова удаляет половину и т. Д.Если вы определяете функцию сравнения для bsearch() с одинаковыми типами для двух аргументов, то qsort() может использовать одну и ту же функцию сравнения.

Функция bsearch() возвращает указатель на найденный элемент массива, который соответствуетключ поиска.Если соответствующий элемент не найден, bsearch() возвращает нулевой указатель. [a]

Пример использования : 

/* bsearch example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort, bsearch, NULL */

int compareints (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int values[] = { 50, 20, 60, 40, 10, 30 };

int main ()
{
  int * pItem;
  int key = 40;
  qsort (values, 6, sizeof (int), compareints);
  pItem = (int*) bsearch (&key, values, 6, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",key);
  return 0;
}

Вывод:

40 находится в массиве.

В ответ на комментарий ниже о том, как найти первый элементэто меньше / больше чем key, вот ( возможно грязный ) обходной путь: вы можете перебрать отсортированный массив и сравнить его элементы с key, используя ту же самую функцию compare, переданную этомуметод, пока вы не найдете элемент меньше / больше, чем key.

3 голосов
/ 11 июля 2019

Библиотека C имеет стандартную функцию bsearch, объявленную в <stdlib.h>, именно для этой цели: найдите соответствующую запись в таблице записей, отсортированных в порядке возрастания в соответствии с заданной функцией сравнения.

Вот спецификация в стандарте C:

7.22.5.1 Функция bsearch

Синопсис 

#include <stdlib.h>
void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));

Описание

Функция bsearch ищет в массиве объектов nmemb, начальный элемент которых указан base, для поиска элемента, который соответствует объекту, указанному key. Размер каждого элемента массива определяется как size.

Функция сравнения, на которую указывает compar, вызывается с двумя аргументами, которые указывают на ключевой объект и на элемент массива в указанном порядке. Функция должна возвращать целое число меньше, равно или больше нуля, если ключевой объект считается, соответственно, меньше, чтобы соответствовать или быть больше, чем элемент массива. Массив должен состоять из: всех элементов, которые сравниваются меньше чем, всех элементов, которые сравниваются равными, и всех элементов, которые сравниваются больше, чем ключевой объект, в этом порядке. 308)

Возвращает

Функция bsearch возвращает указатель на соответствующий элемент массива или нулевой указатель, если совпадение не найдено. Если два элемента сравниваются как равные, сопоставляемый элемент не указывается.

308) На практике весь массив сортируется в соответствии с функцией сравнения.

Эта функция имеет 2 недостатка:

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

Вот простая реализация, которая фиксирует первую точку (она кодируется так, чтобы всегда возвращать совпадающую запись, ближайшую к началу массива) и может быть изменена для обращения ко второй: 

#include <stdlib.h>

void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *))
{
    const unsigned char *p;
    size_t m;
    int r;

    while (nmemb > 0) {
        m = (nmemb - 1) >> 1;
        p = (const unsigned char *)base + m * size;
        if ((r = compar(key, p)) < 0) {
            nmemb = m;
        } else
        if (r > 0) {
            base = p + size;
            nmemb -= m + 1;
        } else
        if (m == 0) {
            return (void *)p;
        } else {
            /* continue search to return first matching entry */
            nmemb = m + 1;
        }
    }
    // if you want the insertion point, you can return p here
    return NULL;
}
...