I have to make a binary search algorithm in Assembly (69HC11) with loops. This is what I have done:
ORG $C400
;n1-n5 will have numbers
N1 RMB 2
N2 RMB 2
N3 RMB 2
N4 RMB 2
N5 RMB 2
IZQ RMB 2
DER RMB 2
;Here is where is going to be the answer
MID RMB 2
;The number im searching
T RMB 2
ORG $C500
LDD #$400
STD IZQ
LDD #$408
STD DER
LOOP: LDD IZQ
ADDD DER
LDX #2
IDIV
STX MID
LDD MID
CPD #T
BLO LAZO1
BHI LAZO2
BEQ LAZO3
LDD IZQ
CPD DER
BLS LOOP
LAZO1:
;izq = mid + 1
INX
STX IZQ
BRA LOOP
LAZO2:
;der = mid - 1
DEX
STX DER
BRA LOOP
LAZO3:
Fin: BRA Fin
The problem is that the loop I want to calculate the mid position and then storage in D the value that is in that position. I tried to write something like $MID but is not posible.
(First of all I have used this assembler: http://www.aspisys.com/asm11.htm It may need some minor syntax adjustments to make it compatible to another assembler. For example, the @@ indicates local symbols within the current PROC.)
It's better to work with simple indices (0..N-1) rather than actual memory addresses which depending on the word size may make it more difficult to calculate the mid point.
For greater simplicity you could use single byte head and tail variables but then your maximum array would be limited to 256 entries. I left it as word, giving a maximum of 64K entries.
I used a static array (residing in ROM) for initialization simplicity. If you want the array to be in RAM, you need to first initialize it with some data, and rather than using DW directives, you should instead use RMB WORD_SIZE*ARRAY_SIZE to allocate the memory area.
There is no need for using global variables at all. You could write the BinarySearch routine so that it can be used with different tables. For example, the target value could be passed in register D, the starting address of the array in register X, and the number of array elements in register Y. Then, your work variables (mid_point, target, head, and tail) could all be dynamically allocated on the stack upon entry to Search, and de-allocated before exit, while load the result (mid_point) into register X (for example).
All registers are destroyed inside BinarySearch. Use PUSH on entry and PULL on exit if you want them protected.
BinarySearch exits with Carry Clear if target is found, and the mid_point variable updated with the related pointer. Carry is Set if target is not found, and mid_point is 'garbage'.