Чтение онлайн

Линейный поиск в значительной степени похож на свое название: вы начинаете в начале и проходите искомый массив, пока не встретите то, что нужно. Для чего-нибудь простого, типа поиска целых, это обычно принимает форму цикла

. Рассмотрите эту функцию:

Преимуществом линейного поиска является его простота; легко с самого начала написать правильный код. Более того, он работает всегда. Даже если в конец массива добавляются элементы или они удаляются из него, нет необходимости сортировать массив.

Недостатком линейного поиска является то, что он медленный. В среднем для массива, содержащего

элементов, при линейном поиске случайного элемента требуется '' сравнений, прежде чем найдется нужный элемент. Это становится чрезмерно дорогим даже на современных высокопроизводительных системах, когда принимает большие значения. Поэтому линейный поиск следует использовать лишь с небольшими массивами.

В отличие от линейного, бинарный поиск требует, чтобы входной массив был уже отсортирован. Недостатком здесь является то, что если добавляются элементы, массив перед новым поиском нужно повторно отсортировать. (Когда элементы удаляются, остальное содержимое массива все равно должно быть перетасовано. Это не так дорого, как повторная сортировка, но все равно может потребовать большого перемещения данных.)

Преимуществом бинарного поиска, и значительным, является то, что бинарный поиск умопомрачительно быстр, требуя самое большее log2(N) сравнений, где N является числом элементов в массиве. Функция

объявлена следующим образом:

Параметры и их назначение сходны с таковыми для

:

Объект, который ищется в массиве.

Начало массива.

Число элементов в массиве.

Размер каждого элемента, полученный с помощью

.

Функция сравнения. Она должна работать таким же образом, как функция сравнения для

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

Если объект не найден,

возвращает . В противном случае она возвращает указатель на найденный объект. Если соответствует более одного объекта, какой из них будет возвращен, не определено. Поэтому, как и в случае с , убедитесь, что функция сравнения принимает во внимание все существенные части искомой структуры данных.

показывает на практике, расширяя использованный ранее пример :

Строки 7–12 определяют

; она та же, что и раньше. Строки 16–29 служат в качестве функции сравнения как для , так и для . Они сравнивают лишь ID сотрудников. Строки 33–37 определяют , которая является удобной функцией для печати структуры, поскольку это делается из разных мест.