Programa 8085 para búsqueda binaria

Prerrequisito – Problema de búsqueda binaria  – Escriba un programa en lenguaje ensamblador en el microprocesador 8085 para encontrar un número dado en la lista de 10 números. Si se encuentra, almacene 1 en la salida, de lo contrario, almacene 2 en la salida. Además, almacene el número de iteraciones y el índice del elemento, si lo encuentra. 

Ejemplo: Sea la lista como sigue: 

Test-1: 
Input: 21H (at 3000H)
Output: 1 (success) in 3001H,
2 (index) in 3002H, and
3 (iteration number) in 3003H.

Test-2: 
Input: 22H (at 3000H)
Output: 2 (failure) in 3001H,
X (don't care) in 3002H, and
4 (iteration before failure) in 3003H 

Suposición: 
suponga que los datos para compararlos se almacenan en 3000H, la lista de números es de 3010H a 3019H y los resultados se almacenan de la siguiente manera: número de iteraciones en 3003H, éxito/fracaso (1/2) en 3001H e índice en 3002H 

Algoritmo – 

1. Mueva 0 a Acumulador y guárdelo en 3003H, para indicar el número de iteraciones hasta el momento.
2. Mueva 0 y 9 a los registros L y H, respectivamente.
3. Cargue los datos a buscar en Acumulador desde 3000H y cámbielos al registro B.
4. Recupere el número de iteraciones de 3003H, increméntelo en uno y guárdelo en 3003H.
5. Mueva el valor del registro H al acumulador y compárelo con el registro L.
6. Si se genera el acarreo, la búsqueda binaria ha terminado, así que salte al paso 20.
7. Agregue el valor del registro L al acumulador y gírelo a la derecha.
8. Almacene el valor del acumulador en el registro C y fuerce el restablecimiento de la bandera de acarreo, si está configurado.
9. Cargue la dirección de inicio de la array en el par de registros DE.
10. Agregue el valor del acumulador al Registro E y almacene el resultado en E.
11. Mueva 0 a Acumulador y use el comando ADC para agregar cualquier posible acarreo generado debido a la adición anterior y guárdelo nuevamente en el Registro D.
12. Cargue el valor al que apunta el par DE y compárelo con el Registro B. Si se genera un acarreo, SALTE al paso 15 y si se establece el indicador Cero, SALTE al paso 17.
13. Mueva el valor del Registro C al Acumulador y disminuya el Acumulador.
14. Mueva el valor del Acumulador a H y SALTE de regreso al paso 4.
15. Mueva el valor del Registro C al Acumulador e incremente el Acumulador.
16. Mueva el valor del Acumulador a L y SALTE de regreso al paso 4.
17. Mueva 1 a la tienda de anuncios Acumulador en 3001H para indicar el éxito.
18. Mueva el valor del Registro C al Acumulador y guárdelo en 3002H para guardar el índice.
19. SALTAR a la afirmación 21.
20. Mueva 2 al Acumulador y guárdelo en 3001H para indicar falla.
21. Finaliza el programa.

Programa – 

Dirección	Etiqueta	Instrucción	Comentario
2000H		LDA 3000H	Cargar valor para buscar
2003H		MOV B, A	Guárdelo en el registro B
2004H		MVI A, 0
2006H		STA 3003H	Número de iteración de la tienda
2009H		M0V L, A
200AH		MVI A, 9
200CH		MOV H, A	Almacenamiento de índices altos y bajos en el par HL hecho
200DH	inicio_bucle:	LDA3003H	Número de iteración de carga
2010H		USD A	Incrementar número de iteración
2011H		STA 3003H	Almacenar en 3003H
2014H		MOV A, H	Almacenar índice alto en Acumulador
2015H		CMP L	Comparar con el índice más bajo
2016H		JC loop_end	Si se genera un acarreo, esto significa que alto es menor que bajo, por lo que la búsqueda binaria sobre
2019H		AÑADIR L	Agregar alto a bajo
202AH		RAR	Gire a la derecha para dividir por dos y generar mid
202BH		MOV C, A	Guardar mid en el registro C
202CH		Restablecimiento de JNC	Si la bandera de transporte no está configurada, vaya directamente a restablecer.
202FH		CMC	Forzar bandera de acarreo desarmada
2030H	Reiniciar	NOP
2031H		LXI D, 3010H	Cargar la dirección de inicio en el par DE
2034H		AÑADIR E	Agregue mid a E para obtener el desplazamiento
2035H		MUEVE UN	Vuelva a obtener la dirección modificada en E para que se convierta en un puntero a arr[mid]
2036H		MVI A, 0	Manejar posible desbordamiento
2038H		ADC D
2039H		MOV D, A	Índice de memoria manejado
203AH		LDAX D	Cargue el elemento de array en el acumulador
203BH		CMP B	Comparar con valor para buscar
203CH		JC else_block	Implica que el valor es mayor que el valor en el medio, por lo que necesitamos bajo = medio + 1
203FH		impresión JZ	Si se establece el indicador cero, se encontró una coincidencia. Saltar al bloque de impresión
2042H		MOV A, C	Ninguno de los dos se ejecutó, por lo que value<mid y necesitamos high=mid-1
2043H		DCR A	medio = medio-1
2044H		MOV H, A	h = medio
2045H		Bucle de inicio de JMP	Saltar atrás
2046H	else_block	MOV A, C	Necesitamos bajo = medio + 1
2047H		USD A	medio = medio + 1
2048H		MOV A, L	l = medio
2049H		Bucle de inicio de JMP
204CH	impresión	MVI A, 1	Mover 1 al acumulador
204EH		STA 3001H	Almacénelo en 3001H para indicar el éxito
2051H		MOV A, C	Mueva el índice, que es medio, de vuelta al Acumulador
2052H		STA 3002H	Guárdelo en 3002H
2055H		JMP true_end	Saltar al final del código
2058H	loop_end	MVI A, 2
205AH		STA 3001H	Almacene 2 en 3001H para indicar falla
205DH	fin_verdadero	HLT	Terminar

Explicación –  

1. Movemos el valor del índice superior e inferior (9 y 0 en este caso) a los registros H y L respectivamente en el paso 2
2. Los índices más altos y más bajos se comparan en el paso 5. Al obtener un acarreo, que indica bajo>alto, saltamos al final del ciclo; de lo contrario, vamos al paso 6.
3. En los pasos 7 y 8, agregamos el valor de los registros H y L y lo rotamos a la derecha, lo que equivale a (alto+bajo)/2 para encontrar el índice en lenguaje C, por ejemplo.
4. En el paso 10, agregamos el valor de mid a la dirección inicial de la array para que actúe como un desplazamiento, similar a cómo *(arr+x) y arr[x] son ​​idénticos en C.
5. El paso 11 garantiza que no se produzca un desbordamiento.
6. En el paso 12, comparamos el valor en el índice medio con el valor a buscar. Si es igual, salimos del bucle y establecemos los valores de forma adecuada.
7. Si no son iguales, el paso 12 se bifurca adecuadamente para permitirnos incrementar/disminuir mid en 1 y mover ese valor al registro L/H, según sea necesario (al igual que high=mid-1 o low=mid+1 se hace en C) y vuelve al inicio del ciclo, ese es el paso 2.

Nota: este enfoque fallará si el elemento que se va a buscar es más pequeño que el elemento más pequeño de la array. Para manejar eso, agregue un cero adicional al comienzo del ciclo y mueva los valores 10 y 1 al par HL en el paso 2, respectivamente.