(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'.
;*******************************************************************************
; Constants
;*******************************************************************************
STACKTOP equ $0DFF
Vreset equ $FFFE
VARS_ORG equ $0300
ARRAY_ORG equ $C400
CODE_ORG equ $C500
;*******************************************************************************
; Variables
;*******************************************************************************
#RAM
org VARS_ORG
mid_point rmb 2 ; eventually holds the answer
target rmb 2 ; the number to search for
head rmb 2 ; head work pointer
tail rmb 2 ; tail work pointer
;*******************************************************************************
; Code
;*******************************************************************************
#ROM
org ARRAY_ORG ;wherever you want your array to be
array dw 1000
WORD_SIZE equ *-array ;bytes per entry in array
dw 2000
dw 3000
dw 4000
dw 5000
dw 6000
dw 7000
dw 8000
dw 9000
ARRAY_SIZE equ *-array/WORD_SIZE
;*******************************************************************************
;org CODE_ORG ;wherever you want your code to be
BinarySearch proc
clra ;D = 0
clrb
std head ;initialize head pointer to zero
ldd #ARRAY_SIZE-1 ;initialize tail pointer to N-1
std tail
Loop@@ ldd head
addd tail
rora ;LSRD will not work if previous
rorb ; ADDD produced a carry
std mid_point ;update mid_point
lsld ;multiply by WORD_SIZE (x2 -- a shift left will do)
addd #array ;offset into array
xgdx ;X = pointer
ldd target ;target number to search for
cpd ,x ;compare against array value
beq Found@@ ;if equal, we're done
bhi Upper@@ ;if greater than, use upper half
; blo Lower@@ ;if less than, use lower half
Lower@@ ldx mid_point ;tail = mid_point - 1
dex
stx tail
bra Cont@@
Upper@@ ldx mid_point ;head = mid_point + 1
inx
stx head
Cont@@ ldx head
cpx tail
bls Loop@@
NotFound@@ sec ;indicates 'not found'
bra Done@@
Found@@ ldd mid_point
lsld
addd #array
std mid_point
clc ;indicates 'found'
Done@@ rts
;*******************************************************************************
Start proc
lds #STACKTOP
ldd #12345
std target
bsr BinarySearch
ldd #5000
std target
bsr BinarySearch
ldd #3000
std target
bsr BinarySearch
bra *
;*******************************************************************************
#VECTORS
org Vreset
dw Start
