Advanced Assembly Programming - The HCS12/9S12: An Introduction to Software and Hardware Interfacing - page 162

Step 5
If key , arr[mean], then set max to mean 2 1 and go to step 2.
Step 6
If key . arr[mean], then set min to mean 1 1 and go to step 2.
The algorithm works for arrays sorted in ascending order, but can be modifi ed to work for arrays
sorted in descending order.

Example 4.6
▼ Write a subroutine to implement the binary search algorithm and a sequence of instruc-
tions to test it. Use an array of n 8-bit elements for implementation.
Solution: In this example, we will use the stack to pass parameters (base address of the array,
array count, and search key) and also allocate local variables in the stack. The stack frame is
shown in Figure 4.9.

mean SP

SP+1
SP+2

min

max

X

B

ret_address

key

SP+8
SP+9
SP+10

arrCnt

arrBase

Figure 4.9 ■ Stack frame for binary search

n equ 30 ; array count

srch equ 69 ; key to be searched

mean equ 0 ; stack offset for local variable mean

min equ 1 ; stack offset for local variable min

max equ 2 ; stack offset for local variable max

key equ 8 ; stack offset for local variable key

arrCnt equ 9 ; stack offset for local variable arrCnt

arrBas equ 10 ; stack offset for local variable arrBas

locvar equ 3 ; number of bytes for local variables

org $1000

result ds.b 1 ; search result

org $1500

lds #$1500

movw #arr,2, 2 SP ; pass array base address

movb #n,1, 2 SP ; pass array count

movb #srch,1, 2 SP ; pass key for search

jsr binsearch

leas 4,SP ; deallocate space used in passing parameters

staa result