Иллюстрированный самоучитель по практике программирования

Поиск

Вот пример массива более реалистичного размера из программы, выполняющей синтаксический разбор текста, написанного на HTML, где определены имена более чем сотни отдельных символов:

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Поиск

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Поиск

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

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

printf("Ta6лица HTML содержит %d слов\n", NELEMS(htmlchars));

Функция двоичного поиска для этой таблицы могла бы выглядеть так:

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Поиск

Объединяя все это вместе, мы можем написать:

half = lookup("frac12", htmlchars, NElEMS(htmlchars));

Для определения индекса, под которым символ 1/2 (одна вторая) стоит в массиве htmlchars.

Двоичный поиск отбрасывает за каждый шаг половину данных, поэтому количество шагов пропорционально тому, сколько раз мы можем поделить п на 2, пока у нас не останется один элемент. Без учета округления это число равно Iog2n. Если у нас в массиве 100"0 элементов, то линейный поиск займет до 1000 шагов, в то время как двоичный – только около 10; при миллионе элементов линейный поиск займет миллион шагов, а двоичный – 20. Очевидно, чем больше число элементов, тем больше преимущество двоичного поиска. Начиная с некоторого зависящего от реализации размера данных, двоичный поиск работает быстрее, чем линейный.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.