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