Двоичный (Бинарный) поиск - 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
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д