TITLE   Binary search of a sorted integer array   BIN_SRCH.ASM
COMMENT |
        Objective: To implement binary search of a sorted
                   integer array.
            Input: Requests numbers to fill array and a 
                   number to be searched for from user.
           Output: Displays the position of the number in
                   the array if found; otherwise, not found
|                  message.
.MODEL SMALL
.STACK 100H
.DATA
MAX_SIZE       EQU 100
array          DW  MAX_SIZE DUP (?)
input_prompt   DB  'Please enter input array (in sorted order): '
               DB  '(negative number terminates input)',0
query_number   DB  'Enter the number to be searched: ',0
out_msg        DB  'The number is at position ',0
not_found_msg  DB  'Number not in the array!',0
query_msg      DB  'Do you want to quit (Y/N): ',0

.CODE
.486
INCLUDE io.mac
main    PROC
        .STARTUP
        PutStr  input_prompt ; request input array
        nwln
        sub     ESI,ESI      ; set index to zero
        mov     CX,MAX_SIZE
array_loop:
        GetInt  AX           ; read an array number
        nwln
        cmp     AX,0            ; negative number?
        jl      exit_loop       ; if so, stop reading numbers
        mov     array[ESI*2],AX ; otherwise, copy into array
        inc     SI           ; increment array index
        loop    array_loop   ; iterates a maximum of MAX_SIZE
exit_loop:
read_input:
        PutStr  query_number ; request number to be searched for
        GetInt  AX           ; read the number
        nwln
        push    AX           ; push number, size & array pointer
        push    SI
        push    OFFSET array
        call    binary_search
        ; binary_search returns in AX the position of the number 
        ; in the array; if not found, it returns 0.
        cmp     AX,0         ; number found?
        je      not_found    ; if not, display number not found
        PutStr  out_msg      ; else, display number position
        PutInt  AX
        jmp     user_query
not_found:
        PutStr  not_found_msg
user_query:
        nwln
        PutStr  query_msg    ; query user whether to terminate
        GetCh   AL           ; read response
        nwln
        cmp     AL,'Y'       ; if response is not 'Y'
        jne     read_input   ; repeat the loop
done:                        ; otherwise, terminate program
        .EXIT
main    ENDP

;-----------------------------------------------------------
; This procedure receives a pointer to an array of integers,
; the array size, and a number to be searched via the stack.
; It returns in AX the position of the number in the array
; if found; otherwise, returns 0.
; All registers, except AX, are preserved.
;-----------------------------------------------------------
binary_search  PROC
       push    BP            ; save registers
       mov     BP,SP
       push    EBX
       push    ESI
       push    CX
       push    DX
       sub     EBX,EBX       ; EBX := 0 
       mov     BX,[BP+4]     ; copy array pointer
       mov     CX,[BP+6]     ; copy array size
       mov     DX,[BP+8]     ; copy number to be searched
       sub     AX,AX         ; lower := 0
       dec     CX            ; upper := size-1
while_loop:
       cmp     AX,CX         ;lower > upper?
       ja      end_while
       sub     ESI,ESI       
       mov     SI,AX         ; middle := (lower + upper)/2
       add     SI,CX
       shr     SI,1
       cmp     DX,[EBX+ESI*2]    ; number = array[middle]?
       je      search_done
       jg      upper_half
lower_half:
       dec     SI            ; middle := middle-1
       mov     CX,SI         ; upper := middle-1
       jmp     while_loop
upper_half:
       inc     SI            ; middle := middle+1
       mov     AX,SI         ; lower := middle+1
       jmp     while_loop
end_while:
       sub     AX,AX         ; number not found (clear AX)
       jmp     skip1
search_done:
       inc     SI            ; position := index+1
       mov     AX,SI         ; return position
skip1:
       pop     DX            ; restore registers
       pop     CX
       pop     ESI
       pop     EBX
       pop     BP
       ret     6
binary_search  ENDP
       END     main