Книга: Linux программирование в примерах
6.2.2. Бинарный поиск: bsearch()
6.2.2. Бинарный поиск: bsearch()
Линейный поиск в значительной степени похож на свое название: вы начинаете в начале и проходите искомый массив, пока не встретите то, что нужно. Для чего-нибудь простого, типа поиска целых, это обычно принимает форму цикла for
. Рассмотрите эту функцию:
/* ifind --- линейный поиск, возвращает найденный индекс или -1 */
int ifind(int x, const int array[], size_t nelems) {
size_t i;
for (i = 0; i < nelems; i++)
if (array(i) == x) /* найдено */
return i;
return -1;
}
Преимуществом линейного поиска является его простота; легко с самого начала написать правильный код. Более того, он работает всегда. Даже если в конец массива добавляются элементы или они удаляются из него, нет необходимости сортировать массив.
Недостатком линейного поиска является то, что он медленный. В среднем для массива, содержащего nelems
элементов, при линейном поиске случайного элемента требуется 'nelems/2
' сравнений, прежде чем найдется нужный элемент. Это становится чрезмерно дорогим даже на современных высокопроизводительных системах, когда nelems
принимает большие значения. Поэтому линейный поиск следует использовать лишь с небольшими массивами.
В отличие от линейного, бинарный поиск требует, чтобы входной массив был уже отсортирован. Недостатком здесь является то, что если добавляются элементы, массив перед новым поиском нужно повторно отсортировать. (Когда элементы удаляются, остальное содержимое массива все равно должно быть перетасовано. Это не так дорого, как повторная сортировка, но все равно может потребовать большого перемещения данных.)
Преимуществом бинарного поиска, и значительным, является то, что бинарный поиск умопомрачительно быстр, требуя самое большее log2(N) сравнений, где N является числом элементов в массиве. Функция bsearch()
объявлена следующим образом:
#include <stdlib.h> /* ISO С */
void *bsearch(const void *key, const void *base, size_t nmemb,
size_t size, int (*compare)(const void*, const void*));
Параметры и их назначение сходны с таковыми для qsort()
:
const void *key
Объект, который ищется в массиве.
const void *base
Начало массива.
size_t nmemb
Число элементов в массиве.
size_t size
Размер каждого элемента, полученный с помощью sizeof
.
int (*compare)(const void*, const void*)
Функция сравнения. Она должна работать таким же образом, как функция сравнения для qsort()
, возвращая отрицательные/нулевые/положительные значения в соответствии с тем, меньше/равен/больше первый параметр по сравнению со вторым.
Если объект не найден, bsearch()
возвращает NULL
. В противном случае она возвращает указатель на найденный объект. Если key
соответствует более одного объекта, какой из них будет возвращен, не определено. Поэтому, как и в случае с qsort()
, убедитесь, что функция сравнения принимает во внимание все существенные части искомой структуры данных.
ch06-searchemp.c
показывает bsearch()
на практике, расширяя использованный ранее пример struct employee
:
1 /* ch06-searchemp.с ---- Демонстрация bsearch(). */
2
3 #include <stdio.h>
4 #include <errno.h>
5 #include <stdlib.h>
6
7 struct employee {
8 char lastname[30];
9 char firstname[30];
10 long emp_id;
11 time_t start_date;
12 };
13
14 /* emp_id_compare --- сравнение по ID */
15
16 int emp_id_compare(const void *e1p, const void *e2p)
17 {
18 const struct employee *e1, *e2;
19
20 e1 = (const struct employee*)e1p;
21 e2 = (const struct employee*)e2p;
22
23 if (e1->emp_id < e2->emp_id)
24 return -1;
25 else if (e1->emp_id == e2->emp_id)
26 return 0;
27 else
28 return 1;
29 }
30
31 /* print_employee --- напечатать структуру сотрудника */
32
33 void print_employee(const struct employee *emp)
34 {
35 printf("%s %st%dt%s", emp->lastname, emp->firstname,
36 emp->emp_id, ctime(&emp->start_date));
37 }
Строки 7–12 определяют struct employee
; она та же, что и раньше. Строки 16–29 служат в качестве функции сравнения как для qsort()
, так и для bsearch()
. Они сравнивают лишь ID сотрудников. Строки 33–37 определяют print_employee()
, которая является удобной функцией для печати структуры, поскольку это делается из разных мест.
39 /* main --- демонстрация сортировки */
40
41 int main(int argc, char **argv)
42 {
43 #define NPRES 10
44 struct employee presidents[NPRES];
45 int i, npres;
46 char buf[BUFSIZ];
47 struct employee *the_pres;
48 struct employee key;
49 int id;
50 FILE *fp;
51
52 if (argc != 2) {
53 fprintf(stderr, "usage: %s datafilen", argv[0]);
54 exit(1);
55 }
56
57 if ((fp = fopen(argv[1], "r")) == NULL) {
58 fprintf(stderr, "%s: %s: could not open: %sn", argv[0],
59 argv[1], strerror(errno));
60 exit(1);
61 }
62
63 /* Очень простой код для чтения данных: */
64 for (npres = 0; npres < NPRES && fgets(buf, BUFSIZ, fp) != NULL;
65 npres++) {
66 sscanf(buf, "%s %s %ld %ld",
67 presidents[npres].lastname,
68 presidents[npres].firstname,
69 &presidents[npres].emp_id,
70 &presidents[npres].start_date);
71 }
72 fclose(fp);
73
74 /* В npres теперь число действительно прочитанных строк. */
75
76 /* Сначала отсортировать по id */
77 qsort(presidents, npres, sizeof(struct employee), emp_id_compare);
78
79 /* Напечатать результат */
80 printf("Sorted by ID:n");
81 for (i = 0; i < npres; i++) {
82 putchar('t');
83 print_employee(&presidents[i]);
84 }
85
86 for (;;) {
87 printf("Enter ID number: ");
88 if (fgets(buf, BUFSIZ, stdin) == NULL)
89 break;
90
91 sscanf(buf, "%dn", &id);
92 key.emp_id = id;
93 the_pres = (struct employee*)bsearch(&key, presidents,
94 npres, sizeof(struct employee), emp_id_compare);
95
96 if (the_pres != NULL) {
97 printf("Found: ");
98 print_employee(the_pres);
99 } else
100 printf("Employee with ID %d not found'n", id);
101 }
102
103 putchar('n'); /* Напечатать в конце символ новой строки. */
104
105 exit(0);
106 }
Функция main()
начинается с проверки аргументов (строки 52–55). Затем она читает данные из указанного файла (строки 57–72). Стандартный ввод для данных сотрудников использоваться не может, поскольку он зарезервирован для запроса у пользователя ID искомого сотрудника.
Строки 77–84 сортируют, а затем печатают данные. Затем программа входит в цикл, начинающийся со строки 86. Она запрашивает идентификационный номер сотрудника, выходя из цикла по достижению конца файла. Для поиска в массиве мы используем struct employee
с именем key
. Достаточно лишь установить в его поле emp_id введенный номер ID; другие поля при сравнении не используются (строка 92).
Если найден элемент с подходящим ключом, bsearch()
возвращает указатель на него. В противном случае она возвращает NULL
. Возвращенное значение проверяется в строке 96, и осуществляется нужное действие. Наконец, строка 102 выводит символ конца строки, чтобы системное приглашение появилось с новой строки. Вот что появляется после компилирования и запуска программы:
$ ch06-searchemp presdata.txt /* Запуск программы */
Sorted by ID:
Carter James 39 Thu Jan 20 13:00:00 1977
Reagan Ronald 40 Tue Jan 20 13:00:00 1981
Bush George 41 Fri Jan 20 13:00:00 1989
Clinton William 42 Wed Jan 20 13:00:00 1993
Bush George 43 Sat Jan 20 13:00:00 2001
Enter ID number: 42 /* Ввод действительного номера */
Found: Clinton William 42 Wed Jan 20 13:00:00 1993 /* Найдено */
Enter ID number: 29 /* Ввод неверного номера */
Employee with ID 29 not found! /* He найдено */
Enter ID number: 40 /* Попытка другого верного номера */
Found: Reagan Ronald 40 Tue Jan 20 13:00:00 1981 /* Этот тоже найден */
Enter ID number: ^D /* CTRL-D в качестве конца файла */
$ /* Готов к приему следующей команды */
Дополнительный, более продвинутый API для поиска коллекций данных описан в разделе 14.4 «Расширенный поиск с использованием двоичных деревьев».
- 6.2. Функции сортировки и поиска
- Бинарный метод
- 13.3.4. Поиск и замена текста
- Фильтры и поиск
- 1.3.1. Индексирование сайта в поисковых системах
- Глава 4 Поиск и выбор идеи
- Глава 1 Поиск (Найдется всё!)
- Нормально ли воспринимается поисковыми системами маскировка партнерских ссылок?
- Общие рекомендации поиска неисправностей
- Поиск и устранение неисправностей модулей памяти
- Поиск источников информации
- Как указать направление поиска в Microsoft Word?