1A. Search a key element in an 'n' number array using Binary search - [VTU 4th sem Mp lab program]

Q) Search a key element in a list of ‘n’ 16 bit numbers using the Binary Search algorithm.

ANS.
This program will search a key element from the given input array and displays the found position if found. Otherwise displays ‘Not found’ message.

Algorithm:
Step1: Initialize low=1,high=n;
Step2: while(low<=high)
           {
      /*Compare low > high if true the element is not found, exit*/
       Find mid
           else
           mid=(low+high)/2;

Step3: if(key==a[mid])
           found & exit;
           else if(key>a[mid])
           low=mid+1;
           else
           high=mid-1;
           }
Step4: Not found.
Step5: Stop.

CODE:

Explanation (Line by line):

.MODEL SMALL
.STACK 64

First line (SMALL) is the assembler directive which states that code has one data and one segment.
Second line defines a stack of 64 length.

.DATA

This Assembler directive defines the data segment of the code.

ARR DW 1234H,1342H,2345H,3456H,4657H

This is an array of numbers, named as ‘ARR’, each number being of Word length (2 bytes) and assigned with 4 immediate values 1234, 1342, 2345, 2456,4657.

LEN DW ($-ARR)/2

This assign the length of the array ‘ARR’ to a memory location ‘LEN’ which is of word length.
Size is calculated as follows,
'$' indicates the current pointer location. (after storing 5 elements in the array ARR) and ARR indicates the base address of the Array. Difference of these must give the length of the array (obvious).

KEY EQU 3456H

Assigns a memory location ‘KEY’ with value 3456. This is the key element we are gonna search for. EQU is the instruction to equate/assign immediate value to a memory location.

Now consider KEY as 3456, ASCII values of all the digits are to be separately found for displaying purpose. Keep a note that ASCII of ‘0’ is 30.

ASCI1 EQU (KEY/1000H)+'0'

See the following calculation,
KEY is divided by 1000 and ASCII value of ‘0’ is added to it, to get the first digit’s ASCII value.
3456/1000 gives 3. Adding 30 to 3 will give 33. Which is ASCII of ‘3’. We got the first digit’s ASCII.
ASCI1=33 now.

ASCI2 EQU (KEY/100H)MOD 10H+'0'

See the following calculation,
KEY is divided by 100 and remainder after dividing the result by 10 is found. ASCII value of ‘0’ is added to it, to get the second digit’s ASCII value.

3456/100 gives 34.
34 mod 10 is 4.
Adding 30 to 4 will give 34.
Which is ASCII of ‘4’.
We got the second digit’s ASCII.

ASCI3 EQU (KEY/10H)MOD 10H+'0'

Similarly,
3456/10=345
345 mod 10 is 5
5+30=35
ASCII of ‘5’ is 35 is found and stored in ASCI3.

ASCI4 EQU (KEY MOD 10H)+'0'

Similarly,
3456 mod 10 =6
6+30=36
ASCII of ‘6’ is 36 is found and stored in ASCI3.

MSG1 DB 10,13,"ELEMENT",ASCI1,ASCI2,ASCI3,ASCI4,"NOT FOUND$”

Defines a memory ‘MSG1’ with the given string value. This message is for ‘not found’ condition.
10,13 is to print a newline character before displaying the not found message.
$ here in the string indicates the end of the string. (just like C program’s null character ‘\0’)

MSG2 DB 10,13,"ELEMENT",' ',ASCI1,ASCI2,ASCI3,ASCI4,' ',"FOUND AT POS"

Similar, MSG2 with appropriate message for found case.

RESULT DB ?,'$'

Memory location for RESULT which is used to store the index of the key element in the array if found. Byte sized and ‘?’ indicates memory is assigned to null/nothing.

.CODE

Assembler directive which defines the code segment of the program.

MOV AX,@DATA
MOV DS,AX

These lines initialize the Data segment. These lines are compulsory in a Microprocessor program which used a data segment.

MOV BX,01H
MOV DX,LEN
MOV CX,KEY

Copy the value 1 to the BX register. Depicts the ‘low’ variable of the algorithm.
Copy the value LEN (length of the string) to the DX register. Depicts the ‘high’ variable of the algorithm.
Copy the value KEY(element to be found) to the CX register. Depicts the ‘key’ variable of the algorithm.

AGAIN:
CMP BX,DX
JA FAIL

Again is a label which will be further used in the code.
CMP instruction compares BX and DX (low and high) and JA FAIL means, if BX is above DX, jump to the label named ‘FAIL’. If BX is below than DX, execution will continue without any jump.

Continue here means to find the middle element in the array. Its done as follows,

MOV AX,BX
ADD AX,DX
SHR AX,01
MOV SI,AX
DEC SI
ADD SI,SI

Consider low is 1 and high is 5. (which is our case)

Now BX is containing low, and DX contains high. First move BX to AX. And then add DX to AX. Which is done in the first two lines of the above snippet. Now find the average. That is divide AX by 2. Shift right by 1 bit will divide a number by 2. This is done in third line of the snippet. AX must now contain the value 3 [(1+5)/2]. Move AX to Stack index register SI. Done in fourth line.

But 3 isn't the actual middle element in the array since each element consumes 2 bytes. Therefore decrease SI and add SI to itself (to double the value of SI). Now SI contains 4, which is the offset address of 3r d element. Done in the last two lines of the above snippet.

CMP CX,ARR[SI]
JAE BIG

Now compare the middle element with the Key element which is present in CX register. You cant directly use KEY here because two parameters can not be memories. If key element is equal or above, move to the right half of the array by changing the value of low to mid+1. This is done in label “BIG”. Jump to label ‘BIG’. Else continue.

DEC AX
MOV DX,AX
JMP AGAIN

In the above comparison,if key is smaller than mid element, search in the lower half of the array. Change high value to mid-1. High is contained in DX. Mid in AX. So AX is decremented by 1(which is mid-1) and moved to DX(high). Then an unconditional jump to ‘AGAIN’ to check the middle element again and perform the search.

BIG:JE SUCCESS
INC AX
MOV BX,AX
JMP AGAIN

Label BIG which is accessed in (key >=mid) condition.
If key is equal to mid element jump to label SUCCESS.
Else BX(low) is assigned to AX+1(which is mid+1). And jump to again. Same is done in the snippet. INC AX and move it to BX. Then jump to AGAIN to search the upper half.

SUCCESS:
ADD AL,'0'
MOV RESULT,AL
LEA DX,MSG2
JMP DISP

If key==mid element, Convert AL to its ASCII by adding ‘0’ to it (for displaying on the screen).
Move the result into RESULT memory location. And load the effective address of success message (MSG2) into DX register. And jump to display part.

FAIL:
LEA DX,MSG1

If all the conditions fail, it means element not found in the array. In that case, load the effective address of failure messASCI1,ASCI2,ASCI3,ASCI4,age (MSG1) into DX register. And proceed.

DISP:
MOV AH,09H
INT 21H
MOV AH,4CH
INT 21H

DISP is a label. Here DOS function ‘09H’ which when moved to AH and on interrupt 21H, will display the message whose offset address is available in DX register, is called. (done in the three lines).
Appropriate messages will be printed at this time on this screen.
Last 2 lines are the terminating statements. ‘4CH’ is service when moved to AH register and on interrupt 21H, will terminate the execution of the program.

END

This assembler directive indicates the end of the code.

OUTPUT:

When you execute this code in the propmt, you will get the message that

"ELEMENT 3456 FOUND AT POS 4"

Since the element '3456' is present at index 4 in the array.

[PS: This code has been explained going very deeply to the concepts. Hope you got the MP basics, Next programs will be explained in a little shorter and better way. ;) ]

Continue to 2A. Reading and displaying string on screen.

Author : Anonymous

He is a simple passionate tech freak who himself is an engineering student at Canara Engineering college. He likes App Development, Web designing, Blogging, Youtubing, Debugging and also is a CodeGeek!