Rosetta Code

Binary search: Difference between revisions

Page Discussion

Binary search (view source)

Revision as of 13:15, 8 July 2023

834 bytes added ,  11 months ago
→‎REXX: Refurbished (and corrected)
(→‎REXX: Refurbished (and corrected))
Line 6,489:
}
}</syntaxhighlight>
=={{header|REXX}}==
=={{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)
<syntaxhighlight lang="rexx"></*REXX program finds a value in a list of integers using an iterative binary search.*/syntaxhighlight>
/*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,▼
list=3 7 19313 19919 22923 23331 24143 27147 28361 29373 31383 31789 337103 349109 353113 359131 383139 389151 401167 409181 421193 433199,
443229 449233 463241 467271 491283 503293 509313 523317 547337 571349 577353 601359 619383 643389 647401 661409 677421 683433 691 709443,
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
/* [↑needle] a list of some low weak primes.*/
parseParse argArg ?needle . /* get a # that's specified on the CL.t*/
If needle=='' Then
if ?=='' Call then do; say; sayexit '***error*** no argument specified.'; say
exit /*stick a fork in it, we're all done. */▼
low= 1▼
end
high= words(@list)▼
▲ low= 1
loc= binarySearchbinarysearch(low, high)▼
▲high= words(@)
If loc==-1 Then
avg= (word(@, 1) + word(@, high)) / 2
499.1 Call exit needle "wasn't found in the list."▼
▲ loc= binarySearch(low, high)
499Say needle "is in the list, its index is:" 41loc'.'▼
 
Exit
if loc==-1 then do; say ? " wasn't found in the list."
/*---------------------------------------------------------------------*/
exit /*stick a fork in it, we're all done. */▼
binarysearch: Procedure Expose list needle
end
Parse Arg i_low,i_high
else say ? ' is in the list, its index is: ' loc▼
If if highi_high<lowi_low Then then return -1 /* the item wasn't found in the @list list. */▼
say
Return-1
say 'arithmetic mean of the ' high " values is: " avg
midi_mid= (low i_low+ highi_high) % 2 /* calculate the midpoint in the list. */▼
exit /*stick a fork in it, we're all done. */▼
y= word(@list, midi_mid) /* obtain the midpoint value in the list */▼
/*──────────────────────────────────────────────────────────────────────────────────────*/
Select
binarySearch: procedure expose @ ?; parse arg low,high
When y=needle Then
▲ if high<low then return -1 /*the item wasn't found in the @ list. */
Return i_mid
▲ mid= (low + high) % 2 /*calculate the midpoint in the list. */
When y>needle Then
▲ y= word(@, mid) /*obtain the midpoint value in the list*/
Return binarysearch(i_low,i_mid-1)
if ?=y then return mid
Otherwise
if y>? then return binarySearch(low, mid-1)
Return binarysearch(i_mid+1,i_high)
return binarySearch(mid+1, high)</syntaxhighlight>
End
exit: Say arg(1)
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 499.1 </tt>}}
▲if loc==-<pre>499.1 then do; say ? " wasn't found in the list."</pre>
<pre>
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 499619 </tt>}}▼
▲499.1 wasn't found in the list.
<pre>619 is in the list, its index is: 53.</pre>
</pre>
 
▲{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 499 </tt>}}
===iterative version===
<pre>
(includes the extra credit)
arithmetic mean of the 74 values is: 510
<syntaxhighlight lang="rexx">/* REXX program finds a value in a list of integers */
/* using an iterative binary search. */
▲@= list=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
/* list: a list of some low weak primes. */
Parse Arg needle /* get a number to be looked for */
If needle=="" Then
Call exit "***error*** no argument specified."
low=1
high=words(list)
Do While low<=high
mid=(low+high)%2
y=word(list,mid)
Select
When y=needle Then
▲ Call exit needle else say ? ' "is in the list, its index is:" mid'.' loc
▲exit When y>needle Then /* too high /*stick a fork in it, we're all done. */
high=mid-1 /* set upper nound */
▲ Otherwise exit/* too low /*stick a fork in it, we're all done. */
▲ low=mid+1 exit/* set lower limit /*stick a fork in it, we're all done. */
End
End
Call exit needle "wasn't found in the list."
 
exit: Say arg(1) </syntaxhighlight>
▲499 is in the list, its index is: 41
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> -314 </tt>}}
<pre>-314 wasn't found in the list.
</pre>
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 619 </tt>}}
<pre>619 is in the list, its index is: 53.</pre>
 
===iterative version===
Walterpachl
2,300

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/346036"