To perform binary search, the array must be sorted. We are taking the lower limit into L and upper limit into H. The array location is stored at DE register pair. The mid is calculated using (H + L)/2. To perform this division, we are just shifting it to the right one time. Then put the mid value into D and check the item located using DE. if the number is same, then jump to end and store 1 at 0101H. This indicates that item is found, and also store the mid value as index. If the mid is not matched, then there are two case, if the number is smaller than the mid element, then it is in the lower half, so the upper limit will be mid – 1, in another case it will be in the other side, so the lower limit will be mid + 1. If the item is not found it will store 02 at location 0101H.
Here Data can be added using the following set of instructions at any place after 0100H, In this code the key element to be searched is stored at 0100H.
| Address | Mnemonics | Comments |
|---|---|---|
| 0000H | MVI A, F8 | Here, F8 in hexadecimal is stored in the accumulator |
| 0002H | STA 0110H | The value F8, which was stored in accumulator is now stored at the address 0110H in memory |
| 0005H | MVI A, 04 | Here, 04 in hexadecimal is stored in the accumulator |
| 0007H | STA 0100H | The value 04 is stored in accumulator as key |
The algorithm can be given as:
| Address | Labels | Mnemonics | Comments |
|---|---|---|---|
| 0000 | LDA 0100H | Load the Key(to be searched) into A | |
| 0003 | MOV B,A | Store the Key into B | |
| 0004 | XRA A | Clear A | |
| 0005 | STA 010H | Store the number of iterations in 0103H | |
| 0008 | MOV L,A | Store A in L | |
| 0009 | MVI H, 09 | Load 9 into H, This is done as I have assumed array to be of length 10 | |
| 000B | START | LDA 0103H | Load the number of iterations into A |
| 000E | INR A | Increment A | |
| 000F | STA 0103H | Restore the number of iterations | |
| 0012 | MOV A, H | Move Upper Limit from H into A | |
| 0013 | CMP L | Compare A and L | |
| 0014 | JC NOTFOUND | If carry=1, jump to NOTFOUND | |
| 0017 | ADD L | Add L to A | |
| 0018 | RAR | Divide A by 2 by rotation to right | |
| 0019 | MOV C, A | Store mid value into C | |
| 001A | JNC RESET | If carry=0, jump to RESET | |
| 001D | CMC | Complement the Carry | |
| 001E | RESET | LXI D, 0110H | Load the initial address of array in DE pair |
| 0021 | ADD E | Add E to mid | |
| 0022 | MOV E, A | Store index at E | |
| 0023 | XRA A | Clear Accumulator | |
| 0024 | ADC D | Add D to A with carry | |
| 0025 | MOV D, A | Restore A into D | |
| 0026 | LDAX D | Load A with the value of mid position | |
| 0027 | CMP B | Compare it with key | |
| 0028 | JC ELSE | If carry=1, jump to ELSE | |
| 002B | JZ PRINT | If zero flag is set jump to PRINT | |
| 002E | MOV A, C | Take mid from C to A | |
| 002F | DCR A | Decrement A | |
| 0030 | MOV H, A | Update the Upper Limit to A-1 | |
| 0031 | JMP START | Jump to Start | |
| 0034 | ELSE | MOV A, C | Load the mid from C to A |
| 0035 | INR A | Increment A | |
| 0036 | MOV L, A | Update Lower Limit with L + 1 | |
| 0037 | JMP START | Jump to Start | |
| 003A | MVI A, 01 | Load 01 as item in found | |
| 003C | STA 0101H | Store the result at 0101H | |
| 003F | MOV A, C | Take the mid from C to A | |
| 0040 | STA 0102H | Store the index of Key into 0102H | |
| 0043 | JMP END | End the task | |
| 0046 | NOTFOUND | MVI A, 02 | Load the 02 into A to indicate that key is not present |
| 0048 | STA 0101H | Store the result at 0102H | |
| 004B | END | HLT | Terminate the program |