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

bne cloop

tst inOrder,sp ; test array inOrder flag after each iteration

bne done
dec iteration,sp
bne ploop
; the following instruction deallocates local variables
done

leas local,sp ; deallocate local variables

pulx

puly

puld

rts

; org $FFFE ; uncomment for CodeWarrior

; dc.w start ; uncomment for CodeWarrior

end

▲

4.6.3 Binary Search Subroutine
Searching is another frequently performed operation. When an array is not sorted, the
search program may need to compare every element of the array. When an array or a file needs
to be searched frequently, it would be more efficient for the programmer to sort the array and
apply a more efficient search method to find the desired element from the array or file.
The binary search algorithm is one of the most efficient search algorithms in use. Suppose
the sorted array (in ascending order) has n elements and is stored at memory locations starting
at the label arr . Let max and min represent the highest and lowest range of array indices to be
searched, and the variable mean represent the average of max and min . The idea of a binary
search algorithm is to divide the sorted array into three parts.
• The upper half. the portion of the array with indices ranging from mean 1 1 to max
• The middle element . the element with index equal to mean
• The lower half . the portion of the array with indices ranging from min to mean 21
The binary search algorithm compares the key with the middle element and takes one of
the following actions on the basis of the comparison result:
• If the key equals the middle element, then stop.
• If the key is larger than the middle element, then the key can be found only in the
upper half of the array. The search will be continued in the upper half.
• If the key is smaller than the middle element, then the key can be found only in
the lower half of the array. The search will be continued in the lower half.
The binary search algorithm can be formulated as follows:
Step 1
Initialize variables max and min to n 2 1 and 0, respectively.
Step 2
If max , min , then stop. No element matches the key.
Step 3
Let mean 5 ( max 1 min )/2.
Step 4
If key equals arr [mean], then key is found in the array; exit.