Linux программирование в примерах
вернуться

Роббинс Арнольд
Шрифт:

/* 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 %s\t%d\t%s", emp->lastname, emp->firstname,

36 emp->emp_id, ctime(&emp->start_date));