Linux программирование в примерах
Шрифт:
6.2.2. Бинарный поиск:
Линейный поиск в значительной степени похож на свое название: вы начинаете в начале и проходите искомый массив, пока не встретите то, что нужно. Для чего-нибудь простого, типа поиска целых, это обычно принимает форму цикла
Преимуществом линейного поиска является его простота; легко с самого начала написать правильный код. Более того, он работает всегда. Даже если в конец массива добавляются элементы или они удаляются из него, нет необходимости сортировать массив.
Недостатком линейного поиска является то, что он медленный. В среднем для массива, содержащего
В отличие от линейного, бинарный поиск требует, чтобы входной массив был уже отсортирован. Недостатком здесь является то, что если добавляются элементы, массив перед новым поиском нужно повторно отсортировать. (Когда элементы удаляются, остальное содержимое массива все равно должно быть перетасовано. Это не так дорого, как повторная сортировка, но все равно может потребовать большого перемещения данных.)
Преимуществом бинарного поиска, и значительным, является то, что бинарный поиск умопомрачительно быстр, требуя самое большее log2(N) сравнений, где N является числом элементов в массиве. Функция
Параметры и их назначение сходны с таковыми для
Объект, который ищется в массиве.
Начало массива.
Число элементов в массиве.
Размер каждого элемента, полученный с помощью
Функция сравнения. Она должна работать таким же образом, как функция сравнения для
Если
Строки 7–12 определяют
Записки духовного авантюриста
Научно-образовательная:
психология
рейтинг книги
Кунсткамера аномалий
Энциклопедия загадочного и неведомого
Документальная литература:
публицистика
рейтинг книги
Экскалибур
3. Хроники Артура
Приключения:
исторические приключения
рейтинг книги
Доброта, чистота помыслов и проникновение в сущность
Религия и эзотерика:
буддизм
рейтинг книги
Неудержимый. Книга XV
15. Неудержимый
Фантастика:
фэнтези
попаданцы
аниме
рейтинг книги
Росс Полдарк
1. Сага о Полдарках
Любовные романы:
исторические любовные романы
рейтинг книги
Феномен Солженицына
Документальная литература:
биографии и мемуары
рейтинг книги