Trying to make a binary search on an ordered array in Motorola 68k assembly

Question

I am trying to find out how to make a binary search subroutine on an ORDERED array, using m68k. For Java, I would do

int binSearch(int key, int &lo, int &hi) 
{
    if (hi < lo)
        return NOT_FOUND;                  //RETURN with V = 1  
    int mid = (lo+hi) / 2;
    if (key == array[mid])
        return mid;
    else if (key < array[mid])             // go left
        return binSearch(key, lo, mid-1);  // left
    else
       return binSearch(key, mid+1, hi);   // right
}

Im trying to put that to assembly. What I have so far is

link        A6,#0
movem.l     D1/A1-A2,-(sp) 
move.w      8(A6),D1   *key t
movea.l     10(A6),A1  *lo
movea.l     14(A6),A2  *hi
cmpa.l      A1,A2 *if hi>lo
BHS            else
move.l      A1,D1 *low D1
add.l       A2,D1 *adds hi
asr.l       #1,D1 * divide by 2

Basically, what do I do at this point? Do I compare D1 to the number im searching for, and then depending on if it is lower and higher, call the subroutine again? Does D1 hold the number at the midway point like I want it to do, or am I wrong? Thank you in advance!

Answer 1

Loop method:

           ORG $1000
START
            LEA       ARRAY,A0     ; start of array
            MOVE.L    #KEY,D0      ; key to find
            MOVE.W    #ELEMENTS,D1 ; length of array
            BSR.S     BINSEARCH
            ; D0 contains mid or -1 if fail
            SIMHALT

BINSEARCH
            MOVE.W     D1,D2       ; high
            MOVEQ      #0,D1       ; low
BINLOOP
            CMP.W      D2,D1       ; hi = low?
            BMI.S      NOT_FOUND
            MOVE.W     D2,D3       
            ADD.W      D1,D3
            LSR.W      #1,D3          ;mid

; there are no scaled index methods on a basic 68k
; check also that word index register addressing works on CPU
; if not some operations will have to be changed to long word

            MOVE.W     D3,D4
            LSL.W      #2,D4          ; *4 for long word
            CMP.L      (A0, D4.W),D0  ; compare mid element to key
            BEQ.S      BIN_FOUND
            BMI.S      SETLO
 SETHI      SUBQ.W     #1,D2
            MOVE.W     D3,D2          ; hi = mid-1

            BRA.S      BINLOOP
 SETLO      ADDQ.W     #1,D3
            MOVE.W     D3,D1          ; lo = mid+1
            BRA.S      BINLOOP
 NOT_FOUND  MOVEQ      #-1,D3           
 BIN_FOUND  MOVE.W     D3,D0          ; return index or -1
            RTS

            ORG $1400
ARRAY       DC.L        1,2,3,4,5,6,7,8,9,10,11
ARRAYEND
ELEMENTS    EQU         (ARRAYEND-ARRAY)/4
KEY         EQU          3