Rosetta Code

Binary search: Difference between revisions

Page Discussion

Binary search (view source)

Revision as of 13:59, 23 June 2019

773 bytes added ,  5 years ago
m
→‎{{header|REXX}}: changed whitespace and comments, used a template for the output sections.
m (→‎{{header|REXX}}: changed whitespace and comments, used a template for the output sections.)
Line 4,886:
=={{header|REXX}}==
===recursive version===
Incidentally, REXX doesn't care if the values in the list are integers (or even numbers), as long as they're in order.
<br><br>(includes the extra credit)
<lang rexx>/*REXX program finds a value in a list of integers using aan recursiveiterative binary search. */
@= 11 3 17 297 3713 4119 5923 6731 7143 7947 9761 101 10773 127 13783 149 16389 179103 163109 179113 131 139 151 167 181,
191193 197199 223229 227233 239241 251271 269283 277293 281313 307317 311337 331349 347353 367359 379383 397389 419401 431409 439421 433,
457443 461449 479463 487467 499491 521503 541509 557523 569547 587571 599577 613601 617619 631643 641647 659661 673677 701683 719691 709,
727743 739761 751773 757797 769811 787823 809829 821839 827859 853863 857883 877887 881911 907919 929941 937953 967 991 1009971 983 1013
/* [↑] a list of strongsome low weak primes.*/
parse arg ? . /*get a number the# user that's specified on the CL.*/
if ?=='' then do; say; say '***error*** no argument specified.'; say
if ?=='' then do
say; say '***exit error! *** no arg specified.'; say /*stick a fork in it, we're all done. */
exit 13end
low = 1▼
end
high = words(@)▼
▲ low = 1
avg= (word(@, 1) + word(@, high)) / 2▼
▲high = words(@)
loc = binarySearch(low, high)▼
▲avg=(word(@,1)+word(@,high))/2
▲ loc = binarySearch(low,high)
 
if loc==-1 then do; say ? " wasn't found in the list."
say ? "wasn't foundexit /*stick a fork in theit, list we're all done." */
exit /*stick a fork in it, we're done.*/▼
end
else say ? ' is in the list, its index is: ' loc
say
say 'arithmetic mean of the ' high " values= is: " avg
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*───────────────────────────────────BINARYSEARCH subroutine────────────*/
binarySearch: procedure expose @ ?; parse arg low,high
if high<low then return -1 /*the item wasn't found in the @ list. */
mid= (low + high) % 2 /*calculate the midpoint in the list. */
mid=(low+high)%2
▲ y= word(@, mid) exit /*stickobtain athe forkmidpoint value in it, we'rethe done.list*/
y=word(@,mid)
if ?=y then return mid
if y>? then return binarySearch(low, mid-1)
return binarySearch(mid+1, high)</lang>
'''{{out|output'''|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 499.1 </tt>}}
<pre>
499.1 wasn't found in the list.
</pre>
'''{{out|output'''|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 499 </tt>}}
<pre>
arithmetic mean of the 74 values= is: 510
 
499 is in the list, its index is: 41
</pre>
 
===iterative version===
(includes the extra credit)
<lang rexx>/*REXX program finds a value in a list of integers using an iterative binary search.*/
@= 3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181,
193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401 409 421 433,
443 449 463 467 491 503 509 523 547 571 577 601 619 643 647 661 677 683 691 709,
743 761 773 797 811 823 829 839 859 863 883 887 911 919 941 953 971 983 1013
/* [↑] a list of some low weak primes.*/
parse arg ? . /*get a number the# user that's specified on the CL.*/
if ?=='' then do; say; say '***error*** no argument specified.'; say
if ?=='' then do
say; say '***exit error! *** no arg specified.'; say13
exit 13
end
low = 1
high = words(@)
say 'arithmetic mean of the ' high " values= is: " (word(@, 1) + word(@, high)) / 2
say
do while low<=high; mid= (low + high) % 2; y= word(@, mid)
 
if ?=y then do
if ?=y then do; say ? ' is in the list, its index is: ' mid
exit /*stick a fork in it, we're all done. */
end
 
if y>? then high= mid - 1 /*too high? */
else low= mid + 1 /*too low? */
end /*while*/
 
say ? " wasn't found in the list." /*stick a fork in it, we're all done. */</lang>
'''{{out|output'''|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> -314 </tt>}}▼
▲ /*stick a fork in it, we're done.*/</lang>
▲'''output''' when using the input of: <tt> -314 </tt>
<pre>
arithmetic mean of the 79 values= is: 508
 
-314 wasn't found in the list.
</pre>
'''{{out|output'''|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 619 </tt>}}
<pre>
arithmetic mean of the 79 values= is: 508
 
619 is in the list, its index is: 53
</pre>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/41800"