Использующая таблицу переходов

В какой-то момент по команде перехода в ячейке 1006 микропро­цессор выйдет из цикла на команду в ячейке 100Е. В этот момент со­держимое пары регистров Н, L будет указывать на строку, содержа­щую начальный адрес нужной программной ветви. Четыре команды служат для загрузки этого начального адреса в регистры Н, L. По­скольку начальный адрес в строке таблицы замещает находившийся в Н, L указатель на саму строку, нужно особо позаботиться о том, чтобы не испортить указатель до того, как будет использована нахо­дящаяся в нем информация. Поэтому старшие разряды начального адреса ветви сначала переносятся в регистр 0, а не прямо в регистр Н. После этого указатель в Н, L увеличивается на 1, чтобы указывать на младшие разряды начального адреса, и эти разряды выбираются в регистр L, поскольку указатель больше не нужен. Затем в регистр Н переносятся старшие разряды начального адреса из регистра 0. На­конец, выполняется команда перехода по косвенному адресу, которая заносит содержимое регистров Н, L на программный счетчик, в ре­зультате чего начнется выполнение нужной программной ветви.

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

Для случая с таблицей переходов, например, на первом шаге нужно проверить, лежит ли нужный начальный адрес в первой чет­верке адресов или во второй. Затем на втором шаге нужно установить, принадлежит ли адрес первой или второй паре в выбранной на первом шаге четверке. На третьем шаге выбор сузится до одного адреса. Легко видеть, что такая процедура требует только трех, а не восьми шагов, соответствующих худшему случаю в описанной ранее процедуре. В об­щем случае, если число альтернатив равно N, то при поиске по двоич­ному дереву число шагов будет равно наименьшему целому числу, которое больше или равно Iog₂ N. При больших N это дает значительную экономию по сравнению с последовательным перебором альтернатив.