binsrch.asm

单片机程序设计基础 随书光盘

;折半查找算法。
DATS	EQU	30H	;线性表首址。
N	EQU	17H	;数据元素个数。
OBJ	DATA	2FH	;查找对象存放单元。
LOWP	DATA	2EH	;低端指针存放单元。
HIGHP	DATA	2DH	;高端指针存放单元。
FIND	BIT	00H	;查找成功标志。

	ORG	0000H
	LJMP	TEST
	
	ORG	100H
TEST:	MOV	DPTR,#LIST;将线性表拷贝到片内RAM中。
	MOV	R0,#DATS
	MOV	R2,#N
COPY:	CLR	A
	MOVC	A,@A+DPTR
	MOV	@R0,A
	INC	DPTR
	INC	R0
	DJNZ	R2,COPY
	MOV	OBJ,#52H;查找对象为52H。
	LCALL	BINSRCH	;调用折半查找算法，查找成功。
	MOV	OBJ,#0CFH;查找对象为0CFH。
	LCALL	BINSRCH	;调用折半查找算法，查找失败。
STOP:	LJMP	STOP

LIST:	DB	07H,15H,2AH,3EH	;测试用有序线性表。
	DB	44H,4FH,52H,64H
	DB	77H,7EH,89H,95H
	DB	9CH,0A2H,0B3H,0BCH
	DB	0C8H,0D4H,0DAH,0E5H
	DB	0EFH,0F3H,0FAH

BINSRCH:MOV	A,#DATS	;取线性表的首址，
	MOV	LOWP,A	;作为初始查找范围的低端。
	ADD	A,#N	;加上单字节数据元素个数，
	DEC	A	;减一，得到线性表最后一个元素的地址。
	MOV	HIGHP,A	;作为初始查找范围的高端。
LOOP:	MOV	A,HIGHP	;取高端地址。
	CLR	C
	SUBB	A,LOWP	;和低端地址比较。
	JNC	LOOP1	;当前查找范围内有数据元素吗？
	CLR	FIND	;查找范围消失，查找过程以失败告终。
	RET		;结束。
LOOP1:	MOV	A,HIGHP	;当前查找范围内有数据元素，取高端地址，
	ADD	A,LOWP	;加上低端地址，
	RRC	A	;平均，
	MOV	R0,A	;得到中间地址。
	MOV	A,@R0	;读取中间元素的数值。
	CLR	C
	SUBB	A,OBJ	;和查找对象比较。
	JZ	OK	;正好是查找对象。
	JC	LOOP2	;不是查找对象，而且数值偏小。
	MOV	A,R0	;不是查找对象，而且数值偏大，取当前的中间地址，
	DEC	A	;减一，
	MOV	HIGHP,A	;作为新的查找范围的高端地址。
	LJMP	LOOP	;继续折半查找。
LOOP2:	MOV	A,R0	;不是查找对象，而且数值偏小，取当前的中间地址，
	INC	A	;加一，
	MOV	LOWP,A	;作为新的低端地址。
	LJMP	LOOP	;继续折半查找。
OK:	SETB	FIND 	;找到找到对象，设立成功标志。
	MOV	A,R0	;将指定对象在线性表中的位置存放在累加器中。
	RET		;返回。

	END