Двоичный поиск

Линейный поиск пригоден для коротких таблиц, но для длинных он слишком медлен. На практике невозможно достигнуть оптимального упорядочения в соответствии с частотой. Преимущества простого и быстрого построения таблицы обесцениваются долгим временем поиска. Поэтому для больших таблиц предпочтительны другие способы организации и методы поиска. Одна из наиболее важных и часто используемых процедур — логарифмический, или двоичный, поиск [5]. В этом методе элементы, таблицы сортируются в соответствии с их ключами. Как такая сортировка может быть выполнена, обсуждается в разд. 9.5. Для настоящего изложения достаточно сказать, что таблица упорядочена. Это означает, что сравнив ключ поиска с ключом любого конкретного элемента, можно определить, равны ли они, или же искомый элемент расположен в таблице ниже или выше этого элемента. После этого только соответствующая половина таблицы проверяется посредством сравнения ключа поиска с некоторым ключом из этой половины. Описанный процесс повторяется до тех пор, пока не будет обнаружено совпадение ключей или же последний оставшийся ключ окажется не равным ключу поиска. В последнем случае в таблице не содержится элемента с таким ключом. Минимального значения 5L можно достичь, если делить таблицу пополам и выполнять сравнение с элементом, расположенным в ее середине (или же с любым из них, если таких элементов два). Если ключи равны, элемент найден. Если не равны, оставшаяся подтаблица (верхняя или нижняя половина исходной таблицы) делится пополам, и процесс повторяется, причем всегда пополам делится оставшаяся часть таблицы. На рис. 5.7 показан двоичный поиск для алфавитных ключей. В машине, для того чтобы определить, какой из ключей больше, двоичные представления букв сравниваются как двоичные числа. Такое упорядочение эквивалентно алфавитному порядку.


Что такое ассемблер? Языки ассемблеров Команды языка ассемблера Код операции Псевдооперации Литералы Свободный формат команд Некоторые типичные команды ассемблера для машин с побайтовой организацией Ассемблеры типа «трансляция — выполнение» Однопроходный ассемблер Двухпроходный ассемблер Символы Подробная блок-схема прохода Подробная блок-схема прохода 2 Пример трансляции Таблицы символов общие замечания Обработка таблицы Линейный поиск Двоичный поиск Сравнение двоичного и линейного способов поиска Метод хеширования Пример хеширования Скученность Назначение макрокоманды Различие между макрокомандами и подпрограммами Форматы макрокоманды Ключевой макрос Макропроцессор	Двоичный поиск Линейный поиск пригоден для коротких таблиц, но для длинных он слишком медлен. На практике невозможно достигнуть оптимального упорядочения в соответствии с частотой. Преимущества простого и быстрого построения таблицы обесцениваются долгим временем поиска. Поэтому для больших таблиц предпочтительны другие способы организации и методы поиска. Одна из наиболее важных и часто используемых процедур — логарифмический, или двоичный, поиск [5]. В этом методе элементы, таблицы сортируются в соответствии с их ключами. Как такая сортировка может быть выполнена, обсуждается в разд. 9.5. Для настоящего изложения достаточно сказать, что таблица упорядочена. Это означает, что сравнив ключ поиска с ключом любого конкретного элемента, можно определить, равны ли они, или же искомый элемент расположен в таблице ниже или выше этого элемента. После этого только соответствующая половина таблицы проверяется посредством сравнения ключа поиска с некоторым ключом из этой половины. Описанный процесс повторяется до тех пор, пока не будет обнаружено совпадение ключей или же последний оставшийся ключ окажется не равным ключу поиска. В последнем случае в таблице не содержится элемента с таким ключом. Минимального значения 5L можно достичь, если делить таблицу пополам и выполнять сравнение с элементом, расположенным в ее середине (или же с любым из них, если таких элементов два). Если ключи равны, элемент найден. Если не равны, оставшаяся подтаблица (верхняя или нижняя половина исходной таблицы) делится пополам, и процесс повторяется, причем всегда пополам делится оставшаяся часть таблицы. На рис. 5.7 показан двоичный поиск для алфавитных ключей. В машине, для того чтобы определить, какой из ключей больше, двоичные представления букв сравниваются как двоичные числа. Такое упорядочение эквивалентно алфавитному порядку.