Binary search: Difference between revisions
m
→{{header|Chapel}}
Deadmarshal (talk | contribs) m (→{{header|Oberon-2}}: Added recursive version too) Tag: Made through Tor |
LalaithMeren (talk | contribs) |
||
| (25 intermediate revisions by 12 users not shown) | |||
Line 1,467:
Value 8 found at index 5
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}}===
Line 1,610 ⟶ 1,666:
UNTIL H%=0
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}}===
<syntaxhighlight lang="basic">'iterative binary search example
define size = 0, search = 0, flag = 0, value = 0
define middle = 0, low = 0, high = 0
dim list[2, 3, 5, 6, 8, 10, 11, 15, 19, 20]
arraysize size, list
let value = 4
gosub binarysearch
let value = 8
gosub binarysearch
let value = 20
gosub binarysearch
end
sub binarysearch
let search = 1
let middle = 0
let low = 0
let high = size
do
if low <= high then
let middle = int((high + low ) / 2)
let flag = 1
if value < list[middle] then
let high = middle - 1
let flag = 0
endif
if value > list[middle] then
let low = middle + 1
let flag = 0
endif
if flag = 1 then
let search = 0
endif
endif
loop low <= high and search = 1
if search = 1 then
let middle = 0
endif
if middle < 1 then
print "not found"
endif
if middle >= 1 then
print "found at index ", middle
endif
return</syntaxhighlight>
{{out| Output}}<pre>not found
found at index 4
found at index 9</pre>
==={{header|FreeBASIC}}===
Line 1,714 ⟶ 1,882:
==={{header|Minimal BASIC}}===
{{trans|ASIC}}
{{works with|Bywater BASIC|3.00}}
{{works with|Commodore BASIC|3.5}}
{{works with|MSX Basic|any}}
{{works with|Nascom ROM BASIC|4.7}}
<syntaxhighlight lang="basic">
Line 1,765 ⟶ 1,935:
690 RETURN
</syntaxhighlight>
==={{header|MSX Basic}}===
The [[#Minimal_BASIC|Minimal BASIC]] solution works without any changes.
==={{header|Palo Alto Tiny BASIC}}===
{{trans|ASIC}}
<syntaxhighlight lang="basic">
10 REM BINARY SEARCH
20 LET N=10
30 REM SORTED DATA
40 LET @(1)=-31,@(2)=0,@(3)=1,@(4)=2,@(5)=2
50 LET @(6)=4,@(7)=65,@(8)=83,@(9)=99,@(10)=782
60 LET X=2;GOSUB 500
70 GOSUB 200
80 LET X=5;GOSUB 500
90 GOSUB 200
100 STOP
190 REM PRINT RESULT
200 IF J<0 PRINT #1,X," IS NOT FOUND.";RETURN
210 PRINT #1,X," IS AT INDEX ",J,".";RETURN
460 REM BINARY SEARCH ALGORITHM
470 REM N - NUMBER OF ELEMENTS
480 REM X - SEARCHED ELEMENT
490 REM RESULT: J - INDEX OF X
500 LET L=0,H=N-1,F=0,M=L
510 IF L>H GOTO 570
520 IF F#0 GOTO 570
530 LET M=L+(H-L)/2
540 IF @(M)<X LET L=M+1;GOTO 510
550 IF @(M)>X LET H=M-1;GOTO 510
560 LET F=1;GOTO 510
570 IF F=0 LET J=-1;RETURN
580 LET J=M;RETURN
</syntaxhighlight>
{{out}}
<pre>
2 IS AT INDEX 4.
5 IS NOT FOUND.
</pre>
==={{header|PureBasic}}===
Line 1,867 ⟶ 2,076:
Value 20 found at index 9
</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}}===
Line 2,254 ⟶ 2,519:
{ p "Not found" }
{ p "Found at index: #{index}" }</syntaxhighlight>
=={{header|Bruijn}}==
<syntaxhighlight lang="bruijn">
:import std/Combinator .
:import std/Math .
:import std/List .
:import std/Option .
binary-search [y [[[[[2 <? 3 none go]]]]] (+0) --(∀0) 0]
go [compare-case eq lt gt (2 !! 0) 1] /²(3 + 2)
eq some 0
lt 5 4 --0 2 1
gt 5 ++0 3 2 1
# example using sorted list of x^3, x=[-50,50]
find [[map-or "not found" [0 : (1 !! 0)] (binary-search 0 1)] lst]
lst take (+100) ((\pow (+3)) <$> (iterate ++‣ (-50)))
:test (find (+100)) ("not found")
:test ((head (find (+125))) =? (+55)) ([[1]])
:test ((head (find (+117649))) =? (+99)) ([[1]])
</syntaxhighlight>
=={{header|C}}==
Line 2,603 ⟶ 2,891:
'''iterative''' -- almost a direct translation of the pseudocode
<syntaxhighlight lang="chapel">proc binsearch(A : [], value)
{
var
while (low <= high)
{
var mid = (low + high) / 2;
Line 2,623 ⟶ 2,913:
{{out}}
4
=={{header|Clojure}}==
'''Recursive'''
Line 2,929 ⟶ 3,220:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
low = 1
high = len a[]
res = 0
while low <= high and res = 0
mid = (low + high) div 2
if a[mid] > val
high = mid - 1
elif a[mid] < val
low = mid + 1
else
res = mid
.
.
.
a[] = [ 2 4 6 8 9 ]
print r
</syntaxhighlight>
Line 3,117 ⟶ 3,408:
(setf low (1+ middle)))
(t (cl-return middle)))))))</syntaxhighlight>
=={{header|EMal}}==
<syntaxhighlight lang="emal">
type BinarySearch:Recursive
fun binarySearch = int by List values, int value
fun recurse = int by int low, int high
if high < low do return -1 end
int mid = low + (high - low) / 2
return when(values[mid] > value,
recurse(low, mid - 1),
when(values[mid] < value,
recurse(mid + 1, high),
mid))
end
return recurse(0, values.length - 1)
end
type BinarySearch:Iterative
fun binarySearch = int by List values, int value
int low = 0
int high = values.length - 1
while low <= high
int mid = low + (high - low) / 2
if values[mid] > value do high = mid - 1
else if values[mid] < value do low = mid + 1
else do return mid
end
end
return -1
end
List values = int[0, 1, 4, 5, 6, 7, 8, 9, 12, 26, 45, 67, 78,
90, 98, 123, 211, 234, 456, 769, 865, 2345, 3215, 14345, 24324]
List matches = int[24324, 32, 78, 287, 0, 42, 45, 99999]
for each int match in matches
writeLine("index is: " +
BinarySearch:Recursive.binarySearch(values, match) + ", " +
BinarySearch:Iterative.binarySearch(values, match))
end
</syntaxhighlight>
{{out}}
<pre>
index is: 24, 24
index is: -1, -1
index is: 12, 12
index is: -1, -1
index is: 0, 0
index is: -1, -1
index is: 10, 10
index is: -1, -1
</pre>
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">%% Task: Binary Search algorithm
Line 4,227 ⟶ 4,568:
]</pre>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''
jq and gojq both have a binary-search builtin named `bsearch`.
In the following, a parameterized filter for performing a binary search of a sorted JSON array is defined.
Specifically, binarySearch(value) will return an index (i.e. offset) of `value` in the array if the array contains the value, and otherwise (-1 - ix), where ix is the insertion point, if the value cannot be found.
binarySearch will always terminate. The inner function is recursive.
<syntaxhighlight lang="jq">def binarySearch(value):
# To avoid copying the array, simply pass in the current low and high offsets
def binarySearch(low; high):
Line 4,243 ⟶ 4,592:
{{Out}}
2
=={{header|Jsish}}==
<syntaxhighlight lang="javascript">/**
Line 4,639 ⟶ 4,989:
</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}}==
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 4,695 ⟶ 5,107:
> PP[ 3 ];
13</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
'''Recursive'''
Line 4,851 ⟶ 5,264:
arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10)
result = binarySearchRecursive arr 6 1 arr.count</syntaxhighlight>
=={{header|Modula-2}}==
{{trans|C}}
{{works with|ADW Modula-2|any (Compile with the linker option ''Console Application'').}}
<syntaxhighlight lang="modula2">
MODULE BinarySearch;
FROM STextIO IMPORT
WriteLn, WriteString;
FROM SWholeIO IMPORT
WriteInt;
TYPE
TArray = ARRAY [0 .. 9] OF INTEGER;
CONST
A = TArray{-31, 0, 1, 2, 2, 4, 65, 83, 99, 782}; (* Sorted data *)
VAR
X: INTEGER;
PROCEDURE DoBinarySearch(A: ARRAY OF INTEGER; X: INTEGER): INTEGER;
VAR
L, H, M: INTEGER;
BEGIN
L := 0; H := HIGH(A);
WHILE L <= H DO
M := L + (H - L) / 2;
IF A[M] < X THEN
L := M + 1
ELSIF A[M] > X THEN
H := M - 1
ELSE
RETURN M
END
END;
RETURN -1
END DoBinarySearch;
PROCEDURE DoBinarySearchRec(A: ARRAY OF INTEGER; X, L, H: INTEGER): INTEGER;
VAR
M: INTEGER;
BEGIN
IF H < L THEN
RETURN -1
END;
M := L + (H - L) / 2;
IF A[M] > X THEN
RETURN DoBinarySearchRec(A, X, L, M - 1)
ELSIF A[M] < X THEN
RETURN DoBinarySearchRec(A, X, M + 1, H)
ELSE
RETURN M
END
END DoBinarySearchRec;
PROCEDURE WriteResult(X, IndX: INTEGER);
BEGIN
WriteInt(X, 1);
IF IndX >= 0 THEN
WriteString(" is at index ");
WriteInt(IndX, 1);
WriteString(".")
ELSE
WriteString(" is not found.")
END;
WriteLn
END WriteResult;
BEGIN
X := 2;
WriteResult(X, DoBinarySearch(A, X));
X := 5;
WriteResult(X, DoBinarySearchRec(A, X, 0, HIGH(A)));
END BinarySearch.
</syntaxhighlight>
{{out}}
<pre>
2 is at index 4.
5 is not found.
</pre>
=={{header|MiniScript}}==
'''Recursive:'''
Line 4,877 ⟶ 5,371:
end while
end function</syntaxhighlight>
=={{header|N/t/roff}}==
Line 6,174 ⟶ 6,669:
}
}</syntaxhighlight>
=={{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.*/
list=3 7
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
If needle=='' Then
Call exit '***error*** no argument specified.'
low=1
high=words(list)
loc=binarysearch(low,high)
If loc==-1 Then
Call exit needle "wasn't found in the list."
Say needle "is in the list, its index is:" loc'.'
Exit
/*---------------------------------------------------------------------*/
binarysearch: Procedure Expose list needle
Parse Arg i_low,i_high
If i_high<i_low Then /* the item wasn't found in the list */
Return-1
i_mid=(i_low+i_high)%2 /* calculate the midpoint in the list */
y=word(list,i_mid) /* obtain the midpoint value in the list */
Select
When y=needle Then
Return i_mid
When y>needle Then
Return binarysearch(i_low,i_mid-1)
Otherwise
Return binarysearch(i_mid+1,i_high)
End
exit: Say arg(1)
{{out|output|text= when using the input of: <tt> 499.1 </tt>}}
<pre>499.1 wasn't found in the list.</pre>
{{out|output|text= when using the input of: <tt> 619 </tt>}}
<pre>619 is in the list, its index is: 53.</pre>
===iterative version===
(includes the extra credit)
<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 "is in the list, its index is:" mid'.'
When y>needle Then /* too high */
high=mid-1 /* set upper nound */
Otherwise /* too low */
low=mid+1 /* set lower limit */
End
End
Call exit needle "wasn't found in the list."
exit: Say arg(1) </syntaxhighlight>
{{out|output|text= when using the input of: <tt> -314 </tt>}}
<pre>-314 wasn't found in the list.
</pre>
{{out|output|text= when using the input of: <tt> 619 </tt>}}
<pre>619 is in the list, its index is: 53.</pre>
===iterative version===
Line 7,326 ⟶ 7,854:
]</syntaxhighlight>
=={{header|Wren}}==
<syntaxhighlight lang="
static recursive(a, value, low, high) {
if (high < low) return -1
Line 7,387 ⟶ 7,915:
70 was not found in the array.
</pre>
=={{header|XPL0}}==
{{trans|C}}
Line 7,476 ⟶ 8,005:
LOCRL R2,R1 Low? => LOW = MID+1
J LOOP }</syntaxhighlight>
=={{header|Zig}}==
'''Works with:''' 0.11.x, 0.12.0-dev.1381+61861ef39
For 0.10.x, replace @intFromPtr(...) with @ptrToInt(...) in these examples.
===With slices===
====Iterative====
<syntaxhighlight lang="zig">pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize {
if (input.len == 0) return null;
if (@sizeOf(T) == 0) return 0;
var view: []const T = input;
const item_ptr: *const T = item_ptr: while (view.len > 0) {
const mid = (view.len - 1) / 2;
const mid_elem_ptr: *const T = &view[mid];
if (mid_elem_ptr.* > search_value)
view = view[0..mid]
else if (mid_elem_ptr.* < search_value)
view = view[mid + 1 .. view.len]
else
break :item_ptr mid_elem_ptr;
} else return null;
const distance_in_bytes = @intFromPtr(item_ptr) - @intFromPtr(input.ptr);
return (distance_in_bytes / @sizeOf(T));
}</syntaxhighlight>
====Recursive====
<syntaxhighlight lang="zig">pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize {
return binarySearchInner(T, input, search_value, @intFromPtr(input.ptr));
}
fn binarySearchInner(comptime T: type, input: []const T, search_value: T, start_address: usize) ?usize {
if (input.len == 0) return null;
if (@sizeOf(T) == 0) return 0;
const mid = (input.len - 1) / 2;
const mid_elem_ptr: *const T = &input[mid];
return if (mid_elem_ptr.* > search_value)
binarySearchInner(T, input[0..mid], search_value, start_address)
else if (mid_elem_ptr.* < search_value)
binarySearchInner(T, input[mid + 1 .. input.len], search_value, start_address)
else
(@intFromPtr(mid_elem_ptr) - start_address) / @sizeOf(T);
}</syntaxhighlight>
===With indexes===
====Iterative====
<syntaxhighlight lang="zig">const math = @import("std").math;
pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize {
if (input.len == 0) return null;
if (@sizeOf(T) == 0) return 0;
var low: usize = 0;
var high: usize = input.len - 1;
return while (low <= high) {
const mid = ((high - low) / 2) + low;
const mid_elem: T = input[mid];
if (mid_elem > search_value)
high = math.sub(usize, mid, 1) catch break null
else if (mid_elem < search_value)
low = mid + 1
else
break mid;
} else null;
}</syntaxhighlight>
====Recursive====
<syntaxhighlight lang="zig">const math = @import("std").math;
pub fn binarySearch(comptime T: type, input: []const T, search_value: T) ?usize {
if (input.len == 0) return null;
if (@sizeOf(T) == 0) return 0;
return binarySearchInner(T, input, search_value, 0, input.len - 1);
}
fn binarySearchInner(comptime T: type, input: []const T, search_value: T, low: usize, high: usize) ?usize {
if (low > high) return null;
const mid = ((high - low) / 2) + low;
const mid_elem: T = input[mid];
return if (mid_elem > search_value)
binarySearchInner(T, input, search_value, low, math.sub(usize, mid, 1) catch return null)
else if (mid_elem < search_value)
binarySearchInner(T, input, search_value, mid + 1, high)
else
mid;
}</syntaxhighlight>
=={{header|zkl}}==
This algorithm is tail recursive, which means it is both recursive and iterative (since tail recursion optimizes to a jump). Overflow is not possible because Ints (64 bit) are a lot bigger than the max length of a list.
| |||