Пособие по практике программирования
Объединяя все это вместе, мы
Объединяя все это вместе, мы можем написать:
half = lookup("frac12", htmlchars, NElEMS(htmlchars));
для определения индекса, под которым символ 1/2 (одна вторая) стоит в массиве htmlchars.
Двоичный поиск отбрасывает за каждый шаг половину данных, поэтому количество шагов пропорционально тому, сколько раз мы можем поделить п на 2, пока у нас не останется один элемент. Без учета округления это число равно Iog2 п. Если у нас в массиве 100"0 элементов, то линейный поиск займет до 1000 шагов, в то время как двоичный — только около 10; при миллионе элементов линейный поиск займет миллион шагов, а двоичный — 20. Очевидно, чем больше число элементов, тем больше преимущество двоичного поиска. Начиная с некоторого зависящего от реализации размера данных, двоичный поиск работает быстрее, чем линейный.
<
