Двоичный (Бинарный) поиск - Assembler
Формулировка задачи:
.data
buffer_for_string db 10 dup(0)
title_string db "Результат: ",0
szformat db "%d",0Dh,0Ah,0 ; изменяем формат вывода на hex
massiv dd 0,1,2,3,4,5,6,7,8
massivD db 1,2,3,4,5,6,7,8 ; костыль
dlinnaMassiva=$-massivD
ZagadannoeChislo dd 3
;===========Code
.code
mov eax,dlinnaMassiva
mov ecx,2
cdq
idiv ecx ; в eax заносится центральный элемент
mov esi,eax
startD:
mov eax,massiv[esi*4]
mov ebx,ZagadannoeChislo
cmp eax,ebx
jl Right
jg Left
je ResultD ; or jmp Result
Right:
mov eax,esi
mov ebx,2
cdq
idiv ebx
add esi,eax
jmp startD
Left:
mov eax,esi
mov ebx,2
cdq
idiv ebx
sub esi,eax
jmp startD
ResultD:
mov Result,eax
;======вывод результата
push Result
push offset szformat
push offset buffer_for_string
call wsprintf
push MB_OK
push offset title_string
push offset buffer_for_string
push 0
call MessageBox
push 0
call ExitProcess
main endp
end startРешение задачи: «Двоичный (Бинарный) поиск»
textual
Листинг программы
/* Если просматриваемый участок непустой, first < last */
while (first < last) {
size_t mid = first + (last - first) / 2;
if (x <= a[mid])
last = mid;
else
first = mid + 1;
}
Объяснение кода листинга программы
- Проверяется условие: если просматриваемый участок не пустой, то есть в нем есть по крайней мере один элемент, то выполняется цикл while.
- Внутри цикла while вычисляется средний индекс участка, который будет использоваться для сравнения:
mid = first + (last - first) / 2. - Сравнивается значение
xс элементом массиваaс индексомmid. - Если
xменьше или равно значению элемента с индексомmid, то выполняется операция присваиванияlast = mid, что означает, что искомый элемент находится в левой половине участка. - Если
xбольше значения элемента с индексомmid, то выполняется операция присваиванияfirst = mid + 1, что означает, что искомый элемент находится в правой половине участка. - Цикл while повторяется до тех пор, пока не будет выполнено одно из условий выхода из цикла.
- Если в процессе выполнения цикла first и last встретились (то есть совпали), это означает, что искомый элемент отсутствует в массиве.
- Если цикл завершился, но first и last не встретились, это означает, что искомый элемент найден, и его индекс равен
mid.