Binary search: Difference between revisions
Content added Content deleted
(→{{header|Modula-2}}: Added a solution.) |
Not a robot (talk | contribs) (Add MACRO-11) |
||
Line 4,954: | Line 4,954: | ||
</syntaxhighlight> |
</syntaxhighlight> |
||
=={{header|MACRO-11}}== |
|||
This deals with the overflow problem when calculating `mid` by using a `ROR` (rotate right) instruction to divide by two, which rotates the carry flag back into the result. `ADD` produces a 17-bit result, with the 17th bit in the carry flag. |
|||
<syntaxhighlight lang="macro11"> .TITLE BINRTA |
|||
.MCALL .TTYOUT,.PRINT,.EXIT |
|||
; TEST CODE |
|||
BINRTA::CLR R5 |
|||
1$: MOV R5,R0 |
|||
ADD #'0,R0 |
|||
.TTYOUT |
|||
MOV R5,R0 |
|||
MOV #DATA,R1 |
|||
MOV #DATEND,R2 |
|||
JSR PC,BINSRC |
|||
BEQ 2$ |
|||
.PRINT #4$ |
|||
BR 3$ |
|||
2$: .PRINT #5$ |
|||
3$: INC R5 |
|||
CMP R5,#^D10 |
|||
BLT 1$ |
|||
.EXIT |
|||
4$: .ASCII / NOT/ |
|||
5$: .ASCIZ / FOUND/ |
|||
.EVEN |
|||
; TEST DATA |
|||
DATA: .WORD 1, 2, 3, 5, 7 |
|||
DATEND = . + 2 |
|||
; BINARY SEARCH |
|||
; INPUT: R0 = VALUE, R1 = LOW PTR, R2 = HIGH PTR |
|||
; OUTPUT: ZF SET IF VALUE FOUND; R1 = INSERTION POINT |
|||
BINSRC: BR 3$ |
|||
1$: MOV R1,R3 |
|||
ADD R2,R3 |
|||
ROR R3 |
|||
CMP (R3),R0 |
|||
BGE 2$ |
|||
ADD #2,R3 |
|||
MOV R3,R1 |
|||
BR 3$ |
|||
2$: SUB #2,R3 |
|||
MOV R3,R2 |
|||
3$: CMP R2,R1 |
|||
BGE 1$ |
|||
CMP (R1),R0 |
|||
RTS PC |
|||
.END BINRTA</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0 NOT FOUND |
|||
1 FOUND |
|||
2 FOUND |
|||
3 FOUND |
|||
4 NOT FOUND |
|||
5 FOUND |
|||
6 NOT FOUND |
|||
7 FOUND |
|||
8 NOT FOUND |
|||
9 NOT FOUND</pre> |
|||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
The calculation of "mid" cannot overflow, since Maple uses arbitrary precision integer arithmetic, and the largest list or array is far, far smaller than the effective range of integers. |
The calculation of "mid" cannot overflow, since Maple uses arbitrary precision integer arithmetic, and the largest list or array is far, far smaller than the effective range of integers. |
||
Line 5,010: | Line 5,072: | ||
> PP[ 3 ]; |
> PP[ 3 ]; |
||
13</syntaxhighlight> |
13</syntaxhighlight> |
||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
'''Recursive''' |
'''Recursive''' |