Binary search: Difference between revisions
Content added Content deleted
m (→{{header|Minimal BASIC}}: {{works with|Bywater BASIC|3.00}}) |
(AddedApplesoft BASIC, Chipmunk Basic, Quite BASIC and MSX Basic) |
||
| Line 1,467: | Line 1,467: | ||
Value 8 found at index 5 |
Value 8 found at index 5 |
||
Value 20 found at index 10 |
Value 20 found at index 10 |
||
==={{header|Applesoft BASIC}}=== |
|||
{{works with|QBasic}} |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|GW-BASIC}} |
|||
{{works with|MSX BASIC}} |
|||
{{works with|Quite BASIC}} |
|||
<syntaxhighlight lang="qbasic">100 REM Binary search |
|||
110 HOME : REM 110 CLS for Chipmunk Basic, MSX Basic, QBAsic and Quite BASIC |
|||
111 REM REMOVE line 110 for Minimal BASIC |
|||
120 DIM a(10) |
|||
130 LET n = 10 |
|||
140 FOR j = 1 TO n |
|||
150 READ a(j) |
|||
160 NEXT j |
|||
170 REM Sorted data |
|||
180 DATA -31,0,1,2,2,4,65,83,99,782 |
|||
190 LET x = 2 |
|||
200 GOSUB 440 |
|||
210 GOSUB 310 |
|||
220 LET x = 5 |
|||
230 GOSUB 440 |
|||
240 GOSUB 310 |
|||
250 GOTO 720 |
|||
300 REM Print result |
|||
310 PRINT x; |
|||
320 IF i < 0 THEN 350 |
|||
330 PRINT " is at index "; i; "." |
|||
340 RETURN |
|||
350 PRINT " is not found." |
|||
360 RETURN |
|||
400 REM Binary search algorithm |
|||
410 REM N - number of elements |
|||
420 REM X - searched element |
|||
430 REM Result: I - index of X |
|||
440 LET l = 0 |
|||
450 LET h = n - 1 |
|||
460 LET f = 0 |
|||
470 LET m = l |
|||
480 IF l > h THEN 590 |
|||
490 IF f <> 0 THEN 590 |
|||
500 LET m = l + INT((h - l) / 2) |
|||
510 IF a(m) >= x THEN 540 |
|||
520 LET l = m + 1 |
|||
530 GOTO 480 |
|||
540 IF a(m) <= x THEN 570 |
|||
550 LET h = m - 1 |
|||
560 GOTO 480 |
|||
570 LET f = 1 |
|||
580 GOTO 480 |
|||
590 IF f = 0 THEN 700 |
|||
600 LET i = m |
|||
610 RETURN |
|||
700 LET i = -1 |
|||
710 RETURN |
|||
720 END</syntaxhighlight> |
|||
==={{header|ASIC}}=== |
==={{header|ASIC}}=== |
||
| Line 1,610: | Line 1,666: | ||
UNTIL H%=0 |
UNTIL H%=0 |
||
IF S%=A%(B%) THEN = B% ELSE = -1</syntaxhighlight> |
IF S%=A%(B%) THEN = B% ELSE = -1</syntaxhighlight> |
||
==={{header|Chipmunk Basic}}=== |
|||
{{works with|Chipmunk Basic|3.6.4}} |
|||
{{works with|QBasic}} |
|||
{{works with|GW-BASIC}} |
|||
<syntaxhighlight lang="qbasic">100 rem Binary search |
|||
110 cls |
|||
120 dim a(10) |
|||
130 n% = 10 |
|||
140 for i% = 0 to 9 : read a(i%) : next i% |
|||
150 rem Sorted data |
|||
160 data -31,0,1,2,2,4,65,83,99,782 |
|||
170 x = 2 : gosub 280 |
|||
180 gosub 230 |
|||
190 x = 5 : gosub 280 |
|||
200 gosub 230 |
|||
210 end |
|||
220 rem Print result |
|||
230 print x; |
|||
240 if indx% >= 0 then print "is at index ";str$(indx%);"." else print "is not found." |
|||
250 return |
|||
260 rem Binary search algorithm |
|||
270 rem N% - number of elements; X - searched element; Result: INDX% - index of X |
|||
280 l% = 0 : h% = n%-1 : found% = 0 |
|||
290 while (l% <= h%) and not found% |
|||
300 m% = l%+int((h%-l%)/2) |
|||
310 if a(m%) < x then l% = m%+1 else if a(m%) > x then h% = m%-1 else found% = -1 |
|||
320 wend |
|||
330 if found% = 0 then indx% = -1 else indx% = m% |
|||
340 return</syntaxhighlight> |
|||
==={{header|Craft Basic}}=== |
==={{header|Craft Basic}}=== |
||
| Line 1,795: | Line 1,881: | ||
{{works with|Bywater BASIC|3.00}} |
{{works with|Bywater BASIC|3.00}} |
||
{{works with|Commodore BASIC|3.5}} |
{{works with|Commodore BASIC|3.5}} |
||
{{works with|MSX Basic|any}} |
|||
{{works with|Nascom ROM BASIC|4.7}} |
{{works with|Nascom ROM BASIC|4.7}} |
||
<syntaxhighlight lang="basic"> |
<syntaxhighlight lang="basic"> |
||
| Line 1,845: | Line 1,932: | ||
690 RETURN |
690 RETURN |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
==={{header|MSX Basic}}=== |
|||
The [[#Minimal_BASIC|Minimal BASIC]] solution works without any changes. |
|||
==={{header|Palo Alto Tiny BASIC}}=== |
==={{header|Palo Alto Tiny BASIC}}=== |
||
| Line 1,983: | Line 2,073: | ||
Value 20 found at index 9 |
Value 20 found at index 9 |
||
</pre> |
</pre> |
||
==={{header|Quite BASIC}}=== |
|||
{{works with|QBasic}} |
|||
{{works with|Applesoft BASIC}} |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|GW-BASIC}} |
|||
{{works with|Minimal BASIC}} |
|||
{{works with|MSX BASIC}} |
|||
<syntaxhighlight lang="qbasic">100 REM Binary search |
|||
110 CLS : REM 110 HOME for Applesoft BASIC : REM REMOVE for Minimal BASIC |
|||
120 DIM a(10) |
|||
130 LET n = 10 |
|||
140 FOR j = 1 TO n |
|||
150 READ a(j) |
|||
160 NEXT j |
|||
170 REM Sorted data |
|||
180 DATA -31,0,1,2,2,4,65,83,99,782 |
|||
190 LET x = 2 |
|||
200 GOSUB 440 |
|||
210 GOSUB 310 |
|||
220 LET x = 5 |
|||
230 GOSUB 440 |
|||
240 GOSUB 310 |
|||
250 GOTO 720 |
|||
300 REM Print result |
|||
310 PRINT x; |
|||
320 IF i < 0 THEN 350 |
|||
330 PRINT " is at index "; i; "." |
|||
340 RETURN |
|||
350 PRINT " is not found." |
|||
360 RETURN |
|||
400 REM Binary search algorithm |
|||
410 REM N - number of elements |
|||
420 REM X - searched element |
|||
430 REM Result: I - index of X |
|||
440 LET l = 0 |
|||
450 LET h = n - 1 |
|||
460 LET f = 0 |
|||
470 LET m = l |
|||
480 IF l > h THEN 590 |
|||
490 IF f <> 0 THEN 590 |
|||
500 LET m = l + INT((h - l) / 2) |
|||
510 IF a(m) >= x THEN 540 |
|||
520 LET l = m + 1 |
|||
530 GOTO 480 |
|||
540 IF a(m) <= x THEN 570 |
|||
550 LET h = m - 1 |
|||
560 GOTO 480 |
|||
570 LET f = 1 |
|||
580 GOTO 480 |
|||
590 IF f = 0 THEN 700 |
|||
600 LET i = m |
|||
610 RETURN |
|||
700 LET i = -1 |
|||
710 RETURN |
|||
720 END</syntaxhighlight> |
|||
==={{header|Run BASIC}}=== |
==={{header|Run BASIC}}=== |
||