%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
