Основы программирования микропроцессоров

Пример 2. На языке ассемблера разработать подпрограмму бинарного поиска заданного элемента в упорядоченном массиве. Элементами массива должны быть беззнаковые целые числа размером слово. Искомый элемент должен быть помещен в регистр AX. Начальный адрес массива по-прежнему должен храниться в регистре DI, а количество элементов – в первом элементе.
Результат поиска должен быть возвращен через регистр SI и флаг CF: если значение не найдено флаг CF должен быть установлен в 1, а регистр SI содержать адрес последнего проверенного элемента; если поиск завершился успешно, флаг CF должен быть сброшен, а SI содержать адрес найденного элемента.


Решение. Процедура бинарного поиска BINSRCH приведена ниже (описание метода приведено в примере 4 главы 1). Она также использует вспомогательную переменную ARR, содержащую начальный адрес массива. Первым действием алгоритма является проверка искомого элемента на выход за границы диапазона. Для этого значение регистра AX сравнивается с первым и последним элементами массива. Если условие выхода за диапазон выполняется, устанавливается флаг CF с помощью команды STC и процедуры завершает работу. В противном случае происходит переход по метке SRCH к началу поиска элемента.
Поскольку слова отстоят друг от друга на расстояние двух байт, при делении отрезка пополам полученный индекс приводится к четному значению. Поиск считается неудачно завершенным, если индекс уменьшился до 2. В начале поиска из первого элемента извлекается количество слов массива и дополняется до ближайшего четного значения.
Затем полученный индекс SI добавляется к адресу начала массива DI. В результате происходит перемещение указателя на середину массива. Средний элемент сравнивается с искомым. Если элемент не равен искомому, поиск продолжится в левой или в правой половине массива.
В обоих случаях проверяется индекс на равенство 2 (признак окончания поиска), выполнение деления индекса SI пополам и дополнение его до ближайшего четного значения. Однако при поиске в левой половине текущий индекс SI вычитается из текущего адреса DI, а при поиске в правой половине – складывается с ним.

ARR DW ? ; начальный адрес списка в памяти

BINSRCH PROC

CMP AX, [DI+2] ; сравнение искомого элемента с первым
JA LAST ; искомое значение превосходит первый элемент
LEA SI, [DI+2] ; иначе извлекаем адрес первого элемента
JE EXITF ; искомый элемент равен первому
STC ; устанавливаем флаг CF (элемент не найден)
EXITF: RET ; выход из подпрограммы
LAST:MOV SI, ES:[DI] ; определяем количество элементов
SHL SI, 1 ; умножаем на 2
ADD SI, DI ; перемещаем указатель на последний элемент
CMP AX, ES:[SI] ; сравнение искомого элемента с последним
JB SRCH ; искомый элемент меньше последнего
JE EXITL ; искомый элемент равен последнему
STC ; устанавливаем флаг CF (элемент не найден)
EXITL: RET ; выход из подпрограммы

SRCH:MOV ARR, DI ; сохранение в памяти адреса начала массива

MOV SI, [DI] ; определяем количество элементов
EVEN:TEST SI, 1 ; проверка на четность индекса
JZ ADDL ; да, индекс четный
INC SI ; приводим индекс к четному значению
ADDL:ADD DI, SI ; определяем индекс середины массива
CMPL:CMP AX, [DI] ; сравниваем искомый элемент со средним
JE EXIT ; если средний элемент равен искомому, выход
JA HIGH ; искомый элемент больше
CMP SI, 2 ; сравниваем индекс с 2
JNE SHRL ; индекс больше 2
NO:STC ; устанавливаем флаг CF (элемент не найден)
JE EXIT ; выход из подпрограммы
SHRL:SHR SI, 1 ; делим индекс пополам
TEST SI, 1 ; проверка на четность
JZ SUBL ; индекс четный
INC SI ; делаем индекс четным
SUBL:SUB DI, SI ; перемещаем указатель назад
JMP CMPL ; переход на очередную проверку
HIGH: CMP SI, 2 ; сравниваем индекс с 2
JE NO ; искомый элемент не найден
SHR SI, 1 ; делим индекс пополам
JMP EVEN
EXIT:MOV SI, DI ; сохраняем адрес последнего сравнения в SI
MOV DI, ARR ; восстанавливаем адрес начала списка
RET ; выход из подпрограммы
BINSRCH ENDP