.TITLE BinarySearch Binary search of list ; Inputs the name of an item and then does a binary search ; of the inventory list called Items to see if the word is ; included in the list. It then prints an appropriate message. ; Register usage: ; R6: Low Lowest subscript currently being considered ; R7: High Highest subscript currently being considered ; R8: Mid Subscript of the middle item in the sublist ; R9: Offset for Items[Mid] ; R10: Address of Items ; Constants: NumItems = 10 ; Number of items in the list Length = 10 ; Number of characters in an item ; Buffers and data: InBuf: .ASCID " " Prompt: .ASCID "What item are you looking for? (In caps) " NotFoundMess: .ASCID "We do not carry that item" FoundMess: .ASCID "That item is in stock" Target: .BLKB 10 ; Save room for target ; Inventory list: Items: .ASCII "BOOK " "COMPUTER " .ASCII "NOTEBOOK " "NOTEPAD " .ASCII "PAPER " "PEN " .ASCII "PENCIL " "PROGRAM " .ASCII "RULER " "TERMINAL " .ENTRY Binary, 0 ; ..... Input the Target ..... Begin: PUSHAW Prompt ; Prompt PUSHAW InBuf ; and input name of CALLS #2, G^Lib$Get_Input; ; desired item MOVC3 #Length, InBuf+8,- Target ; and move it to Target ; ..... Initialize binary search for Target ..... MOVL #0, R6 ; Initialize Low MOVL #NumItems-1, R7 ; Initialize High MOVAB Items, R10 ; Init. address of Items ; ..... Main search loop ..... Loop: CMPL R6, R7 ; If Low > High then BGTR NotFound ; branch to NotFound ADDL3 R6, R7, R8 ; Mid gets average of Low DIVL2 #2, R8 ; and High MULL3 #Length, R8, R9 ; Calc. offset for Mid CMPC3 #Length, (R10)[R9], Target ; If found BEQL Found ; branch to Found BLSS AboveMid ; If Item[Mid] < Target ; branch to AboveMid SUBL3 #1, R8, R7 ; else update High BRB Loop ; and branch back to Loop AboveMid: ADDL3 #1, R8, R6 ; Update Low BRB Loop ; and branch back to Loop ; ..... Search failed - Output not found message ..... NotFound: PUSHAW NotFoundMess CALLS #1, G^Lib$Put_Output; BRB Done ; ..... Success - Output found message ..... Found: PUSHAQ FoundMess CALLS #1, G^Lib$Put_Output Done: $EXIT_S .END Binary