折半查找算法的程序段如下:
dseg segment
start_addr dw ?
dseg ends
cseg segment
b_search proc far
assume cs:cseg,ds:dseg
push ds
push ax
mov ax,dseg
mov ds,ax
pop ax
cmp ax,es:[di+2]
; (ax)与第一个元素比较
ja chk_last ; (ax)大于第一个元素则转到chk_last
lea si,es:[di+2] ; 第一个元素地址送si
je exit ; (ax)等于第一个元素则找到退出
stc ; (ax)小于第一个元素则给cf置1
jmp exit ; 未找到退出
chk_last:
mov si,es:[di] ; 数组长度送si
shl si,1 ; (si)*2
add si,di ; si中存放最后一个元素的地址
cmp ax,es:[si] ; (ax)与最后一个元素比较
jb search ; (ax)小于最后一个元素则转到search
je exit ; (ax)等于最后一个元素则找到退出
stc ; (ax)大于最后一个元素则给cf置1
jmp exit ; 未找到退出
; (ax)大于第一个元素而小于最后一个元素
search: mov start_addr,di ; 把数组首地址存入内存单元start_addr
mov si,es:[di] ; 数组长度送si以形成中间元素下标
even_idx:
test si,1 ; (si)是否为偶数
jz add_idx ; (si)为偶数则转add_idx
inc si ; (si)为奇数则加1变成偶数
add_idx: add di,si ; 计算中间元素地址
compare: cmp ax,es:[di] ; (ax)与中间元素比较
je all_done ; 相等则找到转all_done
ja higher ; 大于则转higher
; 在低半部查找
cmp si,2 ; (si)=2?
jne idx_ok ; 不等转idx_ok
no_match:
stc ; (si)=2查找失败给cf置1
je all_done ; 转all_done
idx_ok: shr si,1 ; (si)/2
test si,1 ; (si)是否为偶数
jz sub_idx ; (si)为偶数则转sub_idx
inc si ; (si)为奇数则加1变成偶数
sub_idx: sub di,si ; 计算中间元素地址
jmp short compare ; 转compare
; 在高半部查找
higher: cmp si,2 ; (si)=2?
je no_match ; (si)=2转no_match
shr si,1 ; (si)/2
jmp short even_idx; 转even_idx
all_done:
mov si,di ; 比较地址送si
mov di,start_addr ; 恢复数组首地址
exit: pop ds
ret
b_search endp
cseg ends
如果数组如下:
LIST DW 12,11,22,33,44,55,66,77,88,99,111,222,333
要求查找的数为(AX)= 55。
数组长度为12,第一次比较的是数组的第六个元素;因55<66,所以第二次用低半部折半查找,比较的是第三个元素33;因55>
33,所以第三次用高半部折半查找,比较的是第五个元素55。这样经过三次比较后,因查找成功而退出程序。
如果要查找的数是(AX)= 57。
则第一次比较的仍是第六个元素66;因57<66,所以第二次用低半部折半查找,比较的是第三个元素33;因57>33,所以第三次用高半部折半查找,比较的是第五个元素55;因55<57,所以第四次用高半部折半查找,比较的又是第六个元素66,因57<66,在转低半部折半查找时,因(SI)=2而以查找失败退出程序。