Binary Search

%OUT-------------------------------------------------------------------------------------------------------------%OUT- Search for an item in a sorted array (ascending order) using binary search    

%out- input: Each term of the array (sorted in ascending order) is accepted from the user       

%out- output: If element is found print "FOUND" with its index number,

else print "NOT FOUND"   

%out – author: Ayon and Ariyam                    

%OUT-------------------------------------------------------------------------------------------------------------

if1

include macrolib.lby

endif

.model small

.stack

.data

array_size equ 6                                          ;assuming array_size to be equal to 6

array db array_size dup(?)                      ;reserving bytes = array_size for the array, uninitialised

ip1 db "Enter array (sorted in ascending order): ","$"                     

;a request to prompt the user for entering terms of the array

ip2 db "Enter element to search: ","$" 

;another request to prompt user for input

op1 db "ELEMENT FOUND AT ","$"                                 ;output message

op2 db "ELEMENT NOT FOUND ","$"                              ;another output message

op3 db "comparing with element index ","$"            ;intermediate output message

heading db "***** BINARY SEARCH *****","$"               ;a heading

.code

main proc

            clrscrn                                                                        ;clearing the screen

            mov dx,0105h

            cursor                                                                         ;setting up the cursor

            showmsg heading                                                 ;displaying heading

           

            mov dx,0303h                                                         ;pointing to next line

            cursor                                                                        ;setting up the cursor

            input_array array,array_size,ip1                         ;accept array from user

           

            mov dx,0503h

            push dx                                                                     ;saving cursor position

            cursor

            showmsg ip2

            input                          ;accepting from user element to be searched, element is in AL           

            pop dx                      ;retrieving current cursor position

           

            mov cx,array_size

            sub cx,01h                ;CH & CL will serve as the 'lower' & 'upper' variables respectively

           

            outer: add dh,02h                                      ;point to next line

                        cursor

                        xor bh,bh                                          ;clearing register BH

                        mov bl,cl                                           ;BL<-upper

                        add bl,ch                                         ;BL<-upper+lower

                        ror bx,1                                              ;BL<-(upper+lower)/2 serving as the

;variable 'mid', right shift is equivalent to ;division by 2

                        xor bh,bh                                          ;clearing BH, because after right

; shift of BX, the bit that goes off is

;inserted in BH at the leftmost position

                        cmp al,array[bx]                ;comparing element with middle item in the array

                        ja lower

                        jb higher

                        mov bh,bl                             ;preparing to call output macro

                        showmsg op1                                  ;element found

                        output                                              ;print output from register BH

                        jmp finish                               ;end the program

                                   

            lower:             mov ch,bl                             ;lower<-mid

                                    inc ch                                                ;lower<-mid+1

                                    jmp comp

                                   

            higher:                       mov cl,bl                   ;upper<-mid

                                    dec cl                                    ;upper<-mid-1

           

            comp:                        mov bh,bl                             ;if upper>=lower, preparing to call output

                                    push ax                                 ;ax and dx are affected when

;showmsg & output are called

                                    push dx                                                        

                                    showmsg op3

                                    output

                                    pop dx

                                    pop ax

                                    cmp cx,00FFh          ;when CX=00FFh, upper=-1, but technically

                                                                        ;upper>lower, so to stop iteration this

;statement is must

                                    je stop                       ;upper=-1 => key not found

                                    cmp cl,ch

                                    jae outer                   ;when upper>=lower

                                   

            stop:   add dh,02h

                        cursor                                                 ;setting cursor for final line

                        showmsg op2                                  ;when upper<lower

           

finish:  exit

main endp

end main