Binary search: Difference between revisions
Add bruijn
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Add bruijn) |
||
(32 intermediate revisions by 15 users not shown) | |||
Line 1:
{{task|Classic CS problems and programs}}
A binary search divides a range of values into halves, and continues to narrow down the field of search until the unknown value is found. It is the classic example of a "divide and conquer" algorithm.
Line 146:
:* [http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken].
<br><br>
=={{header|11l}}==
<syntaxhighlight lang="11l">F binary_search(l, value)
V low = 0
V high = l.len - 1
Line 160 ⟶ 159:
R mid
R -1</syntaxhighlight>
=={{header|360 Assembly}}==
<syntaxhighlight lang="360asm">* Binary search 05/03/2017
BINSEAR CSECT
USING BINSEAR,R13 base register
Line 238 ⟶ 236:
229 found at 23
</pre>
=={{header|8080 Assembly}}==
Line 247 ⟶ 244:
Test code is included, which will loop through the values [0..255] and report for each number whether it was in the array or not.
<syntaxhighlight lang="8080asm"> org 100h ; Entry for test code
jmp test
Line 352 ⟶ 349:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang=
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program binSearch64.s */
Line 601 ⟶ 598:
Value find at index : 8
</pre>
=={{header|ACL2}}==
<syntaxhighlight lang=
(cons name
(compress1 name
Line 665 ⟶ 661:
(defarray 'haystack *dim* 0)
*dim*)))</syntaxhighlight>
=={{header|Action!}}==
<syntaxhighlight lang=
INT low,high,mid
Line 723 ⟶ 718:
[-6 0 1 2 5 6 8 9] 7 not found
</pre>
=={{header|Ada}}==
Both solutions are generic. The element can be of any comparable type (such that the operation < is visible in the instantiation scope of the function Search). Note that the completion condition is different from one given in the pseudocode example above. The example assumes that the array index type does not overflow when mid is incremented or decremented beyond the corresponding array bound. This is a wrong assumption for Ada, where array bounds can start or end at the very first or last value of the index type. To deal with this, the exit condition is rather directly expressed as crossing the corresponding array bound by the coming interval middle.
;Recursive:
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Recursive_Binary_Search is
Line 782 ⟶ 776:
end Test_Recursive_Binary_Search;</syntaxhighlight>
;Iterative:
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Binary_Search is
Line 847 ⟶ 841:
2 4 6 8 9 does not contain 5
</pre>
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">BEGIN
MODE ELEMENT = STRING;
Line 906 ⟶ 899:
"ZZZ" near index 8
</pre>
=={{header|ALGOL W}}==
Ieterative and recursive binary search procedures, from the pseudo code. Finds the left most occurance/insertion point.
<syntaxhighlight lang="algolw">begin % binary search %
% recursive binary search, left most insertion point %
integer procedure binarySearchLR ( integer array A ( * )
Line 969 ⟶ 961:
iterative search suggests insert 24 at 5
</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang=
⎕IO(⍺{ ⍝ first lower bound is start of array
⍵<⍺:⍬ ⍝ if high < low, we didn't find it
Line 983 ⟶ 974:
}
</syntaxhighlight>
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">on binarySearch(n, theList, l, r)
repeat until (l = r)
set m to (l + r) div 2
Line 1,017 ⟶ 1,007:
The first occurrence of 7 in range 7 thru 12 of the list is at index 7
7 is not in range 1 thru 5 of the list"</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang=
/* ARM assembly Raspberry PI */
Line 1,298 ⟶ 1,287:
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">binarySearch: function [arr,val,low,high][
if high < low -> return ø
mid: shr low+high 1
Line 1,329 ⟶ 1,317:
found 24324 at index: 24
99999 not found</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang=
StringSplit, A, array, `, ; creates associative array
MsgBox % x := BinarySearch(A, 4, 1, A0) ; Recursive
Line 1,364 ⟶ 1,351:
Return not_found
}</syntaxhighlight>
=={{header|AWK}}==
{{works with|Gawk}}
Line 1,370 ⟶ 1,356:
{{works with|Nawk}}
'''Recursive'''
<syntaxhighlight lang="awk">function binary_search(array, value, left, right, middle) {
if (right < left) return 0
middle = int((right + left) / 2)
Line 1,379 ⟶ 1,365:
}</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="awk">function binary_search(array, value, left, right, middle) {
while (left <= right) {
middle = int((right + left) / 2)
Line 1,388 ⟶ 1,374:
return 0
}</syntaxhighlight>
=={{header|Axe}}==
'''Iterative'''
Line 1,394 ⟶ 1,379:
BSEARCH takes 3 arguments: a pointer to the start of the data, the data to find, and the length of the array in bytes.
<syntaxhighlight lang="axe">Lbl BSEARCH
0→L
r₃-1→H
Line 1,415 ⟶ 1,400:
{{works with|FreeBASIC}}
{{works with|RapidQ}}
<syntaxhighlight lang="freebasic">FUNCTION binary_search ( array() AS Integer, value AS Integer, lo AS Integer, hi AS Integer) AS Integer
DIM middle AS Integer
Line 1,435 ⟶ 1,420:
{{works with|FreeBASIC}}
{{works with|RapidQ}}
<syntaxhighlight lang="freebasic">FUNCTION binary_search ( array() AS Integer, value AS Integer, lo AS Integer, hi AS Integer) AS Integer
DIM middle AS Integer
Line 1,455 ⟶ 1,440:
The following program can be used to test both recursive and iterative version.
<syntaxhighlight lang="freebasic">SUB search (array() AS Integer, value AS Integer)
DIM idx AS Integer
Line 1,482 ⟶ 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}}===
<syntaxhighlight lang="basic">
REM Binary search
DIM A(10)
Line 1,551 ⟶ 1,592:
5 is not found.
</pre>
==={{header|BASIC256}}===
====Recursive Solution====
<syntaxhighlight lang="basic256">function binarySearchR(array, valor, lb, ub)
if ub < lb then
return false
else
mitad = floor((lb + ub) / 2)
if valor < array[mitad] then return binarySearchR(array, valor, lb, mitad-1)
if valor > array[mitad] then return binarySearchR(array, valor, mitad+1, ub)
if valor = array[mitad] then return mitad
end if
end function</syntaxhighlight>
====Iterative Solution====
<syntaxhighlight lang="basic256">function binarySearchI(array, valor)
lb = array[?,]
ub = array[?]
while lb <= ub
mitad = floor((lb + ub) / 2)
begin case
case array[mitad] > valor
ub = mitad - 1
case array[mitad] < valor
lb = mitad + 1
else
return mitad
end case
end while
return false
end function</syntaxhighlight>
'''Test:'''
<syntaxhighlight lang="basic256">items = 10e5
dim array(items)
for n = 0 to items-1 : array[n] = n : next n
t0 = msec
print binarySearchI(array, 3)
print msec - t0; " millisec"
t1 = msec
print binarySearchR(array, 3, array[?,], array[?])
print msec - t1; " millisec"
end</syntaxhighlight>
{{out}}
<pre>3
839 millisec
3
50 millisec</pre>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> DIM array%(9)
array%() = 7, 14, 21, 28, 35, 42, 49, 56, 63, 70
Line 1,576 ⟶ 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}}===
<syntaxhighlight lang="freebasic">function binsearch( array() as integer, target as integer ) as integer
'returns the index of the target number, or -1 if it is not in the array
dim as uinteger lo = lbound(array), hi = ubound(array), md = (lo + hi)\2
Line 1,590 ⟶ 1,792:
return -1
end function</syntaxhighlight>
=== {{header|GW-BASIC}} ===
{{trans|ASIC}}
{{works with|BASICA}}
<syntaxhighlight lang="gwbasic">
10 REM Binary search
20 DIM A(10)
30 N% = 10
40 FOR I% = 0 TO 9: READ A(I%): NEXT I%
50 REM Sorted data
60 DATA -31, 0, 1, 2, 2, 4, 65, 83, 99, 782
70 X = 2: GOSUB 500
80 GOSUB 200
90 X = 5: GOSUB 500
100 GOSUB 200
110 END
190 REM Print result
200 PRINT X;
210 IF INDX% >= 0 THEN PRINT "is at index"; STR$(INDX%);"." ELSE PRINT "is not found."
220 RETURN
480 REM Binary search algorithm
490 REM N% - number of elements; X - searched element; Result: INDX% - index of X
500 L% = 0: H% = N% - 1: FOUND% = 0
510 WHILE (L% <= H%) AND NOT FOUND%
520 M% = L% + (H% - L%) \ 2
530 IF A(M%) < X THEN L% = M% + 1 ELSE IF A(M%) > X THEN H% = M% - 1 ELSE FOUND% = -1
540 WEND
550 IF FOUND% = 0 THEN INDX% = -1 ELSE INDX% = M%
560 RETURN
</syntaxhighlight>
{{out}}
<pre>
2 is at index 4.
5 is not found.
</pre>
==={{header|IS-BASIC}}===
<syntaxhighlight lang=
110 RANDOMIZE
120 NUMERIC ARR(1 TO 20)
Line 1,619 ⟶ 1,856:
350 IF BO<=UP THEN LET SEARCH=K
360 END DEF</syntaxhighlight>
==={{header|Liberty BASIC}}===
<syntaxhighlight lang="lb">
dim theArray(100)
for i = 1 to 100
theArray(i) = i
next i
print binarySearch(80,30,90)
wait
FUNCTION binarySearch(val, lo, hi)
IF hi < lo THEN
binarySearch = 0
ELSE
middle = int((hi + lo) / 2):print middle
if val < theArray(middle) then binarySearch = binarySearch(val, lo, middle-1)
if val > theArray(middle) then binarySearch = binarySearch(val, middle+1, hi)
if val = theArray(middle) then binarySearch = middle
END IF
END FUNCTION
</syntaxhighlight>
==={{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=
10 REM Binary search
20 LET N = 10
Line 1,656 ⟶ 1,918:
520 LET F = 0
530 LET M = L
540 IF L > H
550
560
570
580
590 GOTO 540
600
610
620
630
640
650
660
670
680
690 RETURN
</syntaxhighlight>
==={{header|
The [[#Minimal_BASIC|Minimal BASIC]] solution works without any changes.
==={{header|Palo Alto Tiny BASIC}}===
{{trans|ASIC}}
<syntaxhighlight lang="basic">
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}}===
Both recursive and iterative procedures are included and called in the code below.
<syntaxhighlight lang="purebasic">#Recursive = 0 ;recursive binary search method
#Iterative = 1 ;iterative binary search method
#NotFound = -1 ;search result if item not found
;Recursive
Procedure R_BinarySearch(Array a(1), value, low, high)
Protected mid
If high < low
ProcedureReturn #NotFound
EndIf
mid = (low + high) / 2
If a(mid) > value
ProcedureReturn R_BinarySearch(a(), value, low, mid - 1)
ElseIf a(mid) < value
ProcedureReturn R_BinarySearch(a(), value, mid + 1, high)
Else
ProcedureReturn mid
EndIf
EndProcedure
;Iterative
Procedure I_BinarySearch(Array a(1), value, low, high)
Protected mid
While low <= high
mid = (low + high) / 2
If a(mid) > value
high = mid - 1
ElseIf a(mid) < value
low = mid + 1
Else
ProcedureReturn mid
EndIf
Wend
ProcedureReturn #NotFound
EndProcedure
Procedure search (Array a(1), value, method)
Protected idx
Select method
Case #Iterative
idx = I_BinarySearch(a(), value, 0, ArraySize(a()))
Default
idx = R_BinarySearch(a(), value, 0, ArraySize(a()))
EndSelect
Print(" Value " + Str(Value))
If idx < 0
PrintN(" not found")
Else
PrintN(" found at index " + Str(idx))
EndIf
EndProcedure
#NumElements = 9 ;zero based count
Dim test(#NumElements)
DataSection
Data.i 2, 3, 5, 6, 8, 10, 11, 15, 19, 20
EndDataSection
;fill the test array
For i = 0 To #NumElements
Read test(i)
Next
If OpenConsole()
PrintN("Recursive search:")
search(test(), 4, #Recursive)
search(test(), 8, #Recursive)
search(test(), 20, #Recursive)
PrintN("")
PrintN("Iterative search:")
search(test(), 4, #Iterative)
search(test(), 8, #Iterative)
search(test(), 20, #Iterative)
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()
EndIf</syntaxhighlight>
Sample output:
<pre>
Recursive search:
Value 4 not found
Value 8 found at index 4
Value 20 found at index 9
Iterative search:
Value 4 not found
Value 8 found at index 4
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}}===
'''Recursive'''
<syntaxhighlight lang="runbasic">dim theArray(100)
global theArray
for i = 1 to 100
theArray(i) = i
next i
print binarySearch(80,30,90)
FUNCTION binarySearch(val, lo, hi)
IF hi < lo THEN
binarySearch = 0
ELSE
middle = (hi + lo) / 2
if val < theArray(middle) then binarySearch = binarySearch(val, lo, middle-1)
if val > theArray(middle) then binarySearch = binarySearch(val, middle+1, hi)
if val = theArray(middle) then binarySearch = middle
END IF
END FUNCTION</syntaxhighlight>
==={{header|TI-83 BASIC}}===
<syntaxhighlight lang="ti83b">PROGRAM:BINSEARC
:Disp "INPUT A LIST:"
:Input L1
:SortA(L1)
:Disp "INPUT A NUMBER:"
:Input A
:1→L
:dim(L1)→H
:int(L+(H-L)/2)→M
:While L<H and L1(M)≠A
:If A>M
:Then
:M+1→L
:Else
:M-1→H
:End
:int(L+(H-L)/2)→M
:End
:If L1(M)=A
:Then
:Disp A
:Disp "IS AT POSITION"
:Disp M
:Else
:Disp A
:Disp "IS NOT IN"
:Disp L1</syntaxhighlight>
==={{header|uBasic/4tH}}===
{{trans|Run BASIC}}
The overflow is fixed - which is a bit of overkill, since uBasic/4tH has only one array of 256 elements.
<syntaxhighlight lang="text">For i = 1 To 100 ' Fill array with some values
@(i-1) = i
Next
Print FUNC(_binarySearch(50,0,99)) ' Now find value '50'
End ' and prints its index
_binarySearch Param(3) ' value, start index, end index
Local(1) ' The middle of the array
If c@ < b@ Then ' Ok, signal we didn't find it
Return (-1)
Else
d@ = SHL(b@ + c@, -1) ' Prevent overflow (LOL!)
If a@ < @(d@) Then Return (FUNC(_binarySearch (a@, b@, d@-1)))
If a@ > @(d@) Then Return (FUNC(_binarySearch (a@, d@+1, c@)))
If a@ = @(d@) Then Return (d@) ' We found it, return index!
EndIf</syntaxhighlight>
==={{header|VBA}}===
'''Recursive version''':
<syntaxhighlight lang="vb">Public Function BinarySearch(a, value, low, high)
'search for "value" in ordered array a(low..high)
'return index point if found, -1 if not found
If high < low Then
BinarySearch = -1 'not found
Exit Function
End If
midd = low + Int((high - low) / 2) ' "midd" because "Mid" is reserved in VBA
If a(midd) > value Then
BinarySearch = BinarySearch(a, value, low, midd - 1)
ElseIf a(midd) < value Then
BinarySearch = BinarySearch(a, value, midd + 1, high)
Else
BinarySearch = midd
End If
End Function</syntaxhighlight>
Here are some test functions:
<syntaxhighlight lang="vb">Public Sub testBinarySearch(n)
Dim a(1 To 100)
'create an array with values = multiples of 10
For i = 1 To 100: a(i) = i * 10: Next
Debug.Print BinarySearch(a, n, LBound(a), UBound(a))
End Sub
Public Sub stringtestBinarySearch(w)
'uses BinarySearch with a string array
Dim a
a = Array("AA", "Maestro", "Mario", "Master", "Mattress", "Mister", "Mistress", "ZZ")
Debug.Print BinarySearch(a, w, LBound(a), UBound(a))
End Sub</syntaxhighlight>
and sample output:
<pre>
stringtestBinarySearch "Master"
3
testBinarySearch "Master"
-1
testBinarySearch 170
17
stringtestBinarySearch 170
-1
stringtestBinarySearch "Moo"
-1
stringtestBinarySearch "ZZ"
7
</pre>
'''Iterative version:'''
<syntaxhighlight lang="vb">Public Function BinarySearch2(a, value)
'search for "value" in array a
'return index point if found, -1 if not found
low = LBound(a)
high = UBound(a)
Do While low <= high
midd = low + Int((high - low) / 2)
If a(midd) = value Then
BinarySearch2 = midd
Exit Function
ElseIf a(midd) > value Then
high = midd - 1
Else
low = midd + 1
End If
Loop
BinarySearch2 = -1 'not found
End Function</syntaxhighlight>
==={{header|VBScript}}===
{{trans|BASIC}}
'''Recursive'''
<syntaxhighlight lang="vb">Function binary_search(arr,value,lo,hi)
If hi < lo Then
binary_search = 0
Else
middle=Int((hi+lo)/2)
If value < arr(middle) Then
binary_search = binary_search(arr,value,lo,middle-1)
ElseIf value > arr(middle) Then
binary_search = binary_search(arr,value,middle+1,hi)
Else
binary_search = middle
Exit Function
End If
End If
End Function
'Tesing the function.
num_range = Array(2,3,5,6,8,10,11,15,19,20)
n = CInt(WScript.Arguments(0))
idx = binary_search(num_range,n,LBound(num_range),UBound(num_range))
If idx > 0 Then
WScript.StdOut.Write n & " found at index " & idx
WScript.StdOut.WriteLine
Else
WScript.StdOut.Write n & " not found"
WScript.StdOut.WriteLine
End If</syntaxhighlight>
{{out}}
'''Note: Array index starts at 0.'''
<pre>
C:\>cscript /nologo binary_search.vbs 4
4 not found
C:\>cscript /nologo binary_search.vbs 8
8 found at index 4
C:\>cscript /nologo binary_search.vbs 20
20 found at index 9
</pre>
==={{header|Visual Basic .NET}}===
'''Iterative'''
<syntaxhighlight lang="vbnet">Function BinarySearch(ByVal A() As Integer, ByVal value As Integer) As Integer
Dim low As Integer = 0
Dim high As Integer = A.Length - 1
Dim middle As Integer = 0
While low <= high
middle = (low + high) / 2
If A(middle) > value Then
high = middle - 1
ElseIf A(middle) < value Then
low = middle + 1
Else
Return middle
End If
End While
Return Nothing
End Function</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="vbnet">Function BinarySearch(ByVal A() As Integer, ByVal value As Integer, ByVal low As Integer, ByVal high As Integer) As Integer
Dim middle As Integer = 0
If high < low Then
Return Nothing
End If
middle = (low + high) / 2
If A(middle) > value Then
Return BinarySearch(A, value, low, middle - 1)
ElseIf A(middle) < value Then
Return BinarySearch(A, value, middle + 1, high)
Else
Return middle
End If
End Function</syntaxhighlight>
==={{header|Yabasic}}===
{{trans|Lua}}
<syntaxhighlight lang="yabasic">sub floor(n)
return int(n + .5)
end sub
sub binarySearch(list(), value)
local low, high, mid
low = 1 : high = arraysize(list(), 1)
while(low <= high)
mid = floor((low + high) / 2)
if list(mid) > value then
high = mid - 1
elsif list(mid) < value then
low = mid + 1
else
return mid
end if
wend
return false
end sub
ITEMS = 10e6
dim list(ITEMS)
for n = 1 to ITEMS
list(n) = n
next n
print binarySearch(list(), 3)
print peek("millisrunning")</syntaxhighlight>
==={{header|ZX Spectrum Basic}}===
{{trans|FreeBASIC}}
Iterative method:
<syntaxhighlight lang="zxbasic">10 DATA 2,3,5,6,8,10,11,15,19,20
20 DIM t(10)
30 FOR i=1 TO 10
40 READ t(i)
50 NEXT i
60 LET value=4: GO SUB 100
70 LET value=8: GO SUB 100
80 LET value=20: GO SUB 100
90 STOP
100 REM Binary search
110 LET lo=1: LET hi=10
120 IF lo>hi THEN LET idx=0: GO TO 170
130 LET middle=INT ((hi+lo)/2)
140 IF value<t(middle) THEN LET hi=middle-1: GO TO 120
150 IF value>t(middle) THEN LET lo=middle+1: GO TO 120
160 LET idx=middle
170 PRINT "Value ";value;
180 IF idx=0 THEN PRINT " not found": RETURN
190 PRINT " found at index ";idx: RETURN
</syntaxhighlight>
=={{header|Batch File}}==
<syntaxhighlight lang="windowsnt">
@echo off & setlocal enabledelayedexpansion
Line 1,773 ⟶ 2,468:
endlocal & exit /b 0
</syntaxhighlight>
=={{header|BQN}}==
BQN has two builtin functions for binary search: <code>⍋</code>(Bins Up) and <code>⍒</code>(Bins Down). This is a recursive method.
<syntaxhighlight lang="bqn">BSearch ← {
BS ⟨a, value⟩:
BS ⟨a, value, 0, ¯1+≠a⟩;
Line 1,792 ⟶ 2,486:
•Show BSearch ⟨8‿30‿35‿45‿49‿77‿79‿82‿87‿97, 97⟩</syntaxhighlight>
<syntaxhighlight lang="text">9</syntaxhighlight>
=={{header|Brat}}==
<syntaxhighlight lang="brat">binary_search = { search_array, value, low, high |
true? high < low
{ null }
Line 1,826 ⟶ 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}}==
<syntaxhighlight lang="c">#include <stdio.h>
int bsearch (int *a, int n, int x) {
Line 1,887 ⟶ 2,602:
5 is not found.
</pre>
=={{header|C sharp|C#}}==
'''Recursive'''
<syntaxhighlight lang="csharp">namespace Search {
using System;
Line 1,962 ⟶ 2,676:
}</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="csharp">namespace Search {
using System;
Line 2,036 ⟶ 2,750:
}</syntaxhighlight>
'''Example'''
<syntaxhighlight lang="csharp">//#define UseRecursiveSearch
using System;
Line 2,114 ⟶ 2,828:
glb = 13
lub = 21</pre>
=={{header|C++}}==
'''Recursive'''
<syntaxhighlight lang="cpp">
template <class T> int binsearch(const T array[], int low, int high, T value) {
if (high < low) {
Line 2,145 ⟶ 2,858:
}</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="cpp">template <class T>
int binSearch(const T arr[], int len, T what) {
int low = 0;
Line 2,161 ⟶ 2,874:
}</syntaxhighlight>
'''Library'''
C++'s Standard Template Library has four functions for binary search, depending on what information you want to get. They all need<syntaxhighlight lang="cpp">#include <algorithm></syntaxhighlight>
The <code>lower_bound()</code> function returns an iterator to the first position where a value could be inserted without violating the order; i.e. the first element equal to the element you want, or the place where it would be inserted.
<syntaxhighlight lang="cpp">int *ptr = std::lower_bound(array, array+len, what); // a custom comparator can be given as fourth arg</syntaxhighlight>
The <code>upper_bound()</code> function returns an iterator to the last position where a value could be inserted without violating the order; i.e. one past the last element equal to the element you want, or the place where it would be inserted.
<syntaxhighlight lang="cpp">int *ptr = std::upper_bound(array, array+len, what); // a custom comparator can be given as fourth arg</syntaxhighlight>
The <code>equal_range()</code> function returns a pair of the results of <code>lower_bound()</code> and <code>upper_bound()</code>.
<syntaxhighlight lang="cpp">std::pair<int *, int *> bounds = std::equal_range(array, array+len, what); // a custom comparator can be given as fourth arg</syntaxhighlight>
Note that the difference between the bounds is the number of elements equal to the element you want.
The <code>binary_search()</code> function returns true or false for whether an element equal to the one you want exists in the array. It does not give you any information as to where it is.
<syntaxhighlight lang="cpp">bool found = std::binary_search(array, array+len, what); // a custom comparator can be given as fourth arg</syntaxhighlight>
=={{header|Chapel}}==
'''iterative''' -- almost a direct translation of the pseudocode
<syntaxhighlight lang="chapel">proc binsearch(A:[], value) {
var low = A.domain.dim(1).low;
var high = A.domain.dim(1).high;
Line 2,199 ⟶ 2,911:
{{out}}
4
=={{header|Clojure}}==
'''Recursive'''
<syntaxhighlight lang="clojure">(defn bsearch
([coll t]
(bsearch coll 0 (dec (count coll)) t))
Line 2,218 ⟶ 2,929:
; so return its index
(= mth t) m)))))</syntaxhighlight>
=={{header|CLU}}==
<syntaxhighlight lang="clu">% Binary search in an array
% If the item is found, returns `true' and the index;
% if the item is not found, returns `false' and the leftmost insertion point
Line 2,288 ⟶ 2,998:
19 found at location 8
20 not found, would be inserted at location 9</pre>
=={{header|COBOL}}==
COBOL's <code>SEARCH ALL</code> statement is implemented as a binary search on most implementations.
<syntaxhighlight lang="cobol"> >>SOURCE FREE
IDENTIFICATION DIVISION.
PROGRAM-ID. binary-search.
Line 2,309 ⟶ 3,018:
.
END PROGRAM binary-search.</syntaxhighlight>
=={{header|CoffeeScript}}==
'''Recursive'''
<syntaxhighlight lang="coffeescript">binarySearch = (xs, x) ->
do recurse = (low = 0, high = xs.length - 1) ->
mid = Math.floor (low + high) / 2
Line 2,321 ⟶ 3,029:
else mid</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="coffeescript">binarySearch = (xs, x) ->
[low, high] = [0, xs.length - 1]
while low <= high
Line 2,331 ⟶ 3,039:
NaN</syntaxhighlight>
'''Test'''
<syntaxhighlight lang="coffeescript">do (n = 12) ->
odds = (it for it in [1..n] by 2)
result = (it for it in \
Line 2,347 ⟶ 3,055:
4 is ordinal of 9
5 is ordinal of 11</pre>
=={{header|Common Lisp}}==
'''Iterative'''
<syntaxhighlight lang="lisp">(defun binary-search (value array)
(let ((low 0)
(high (1- (length array))))
Line 2,365 ⟶ 3,072:
(t (return middle)))))))</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="lisp">(defun binary-search (value array &optional (low 0) (high (1- (length array))))
(if (< high low)
nil
Line 2,377 ⟶ 3,084:
(t middle)))))</syntaxhighlight>
=={{header|Crystal}}==
'''Recursive'''
<syntaxhighlight lang="ruby">class Array
def binary_search(val, low = 0, high = (size - 1))
return nil if high < low
Line 2,406 ⟶ 3,112:
end</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="ruby">class Array
def binary_search_iterative(val)
low, high = 0, size - 1
Line 2,443 ⟶ 3,149:
99999 not found in array
</pre>
=={{header|D}}==
<syntaxhighlight lang="d">import std.stdio, std.array, std.range, std.traits;
/// Recursive.
Line 2,495 ⟶ 3,200:
=={{header|Delphi}}==
See [[#Pascal]].
=={{header|E}}==
<syntaxhighlight lang="e">/** Returns null if the value is not found. */
def binarySearch(collection, value) {
var low := 0
Line 2,511 ⟶ 3,215:
return null
}</syntaxhighlight>
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
proc binSearch val . a[] res .
while
low = mid + 1
.
.
.
a[] = [ 2 4 6 8 9 ]
print r
</syntaxhighlight>
=={{header|Eiffel}}==
Line 2,536 ⟶ 3,241:
The following solution is based on the one described in: C. A. Furia, B. Meyer, and S. Velder. ''Loop Invariants: Analysis, Classification, and Examples''. ACM Computing Surveys, 46(3), Article 34, January 2014. (Also available at http://arxiv.org/abs/1211.4470). It includes detailed loop invariants and pre- and postconditions, which make the running time linear (instead of logarithmic) when full contract checking is enabled.
<syntaxhighlight lang=
APPLICATION
Line 2,656 ⟶ 3,361:
end</syntaxhighlight>
=={{header|Elixir}}==
<syntaxhighlight lang="elixir">defmodule Binary do
def search(list, value), do: search(List.to_tuple(list), value, 0, length(list)-1)
Line 2,689 ⟶ 3,393:
99999 not found in list
</pre>
=={{header|Emacs Lisp}}==
<syntaxhighlight lang="lisp">
(defun binary-search (value array)
(let ((low 0)
Line 2,702 ⟶ 3,405:
(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=
%% Author: Abhay Jain
Line 2,731 ⟶ 3,483:
end
end.</syntaxhighlight>
=={{header|Euphoria}}==
===Recursive===
<syntaxhighlight lang="euphoria">function binary_search(sequence s, object val, integer low, integer high)
integer mid, cmp
if high < low then
Line 2,751 ⟶ 3,502:
end function</syntaxhighlight>
===Iterative===
<syntaxhighlight lang="euphoria">function binary_search(sequence s, object val)
integer low, high, mid, cmp
low = 1
Line 2,768 ⟶ 3,519:
return 0 -- not found
end function</syntaxhighlight>
=={{header|F Sharp|F#}}==
Generic recursive version, using #light syntax:
<syntaxhighlight lang="fsharp">let rec binarySearch (myArray:array<IComparable>, low:int, high:int, value:IComparable) =
if (high < low) then
null
Line 2,783 ⟶ 3,533:
else
myArray.[mid]</syntaxhighlight>
=={{header|Factor}}==
Factor already includes a binary search in its standard library. The following code offers an interface compatible with the requirement of this task, and returns either the index of the element if it has been found or f otherwise.
<syntaxhighlight lang="factor">USING: binary-search kernel math.order ;
: binary-search ( seq elt -- index/f )
[ [ <=> ] curry search ] keep = [ drop f ] unless ;</syntaxhighlight>
=={{header|FBSL}}==
FBSL has built-in QuickSort() and BSearch() functions:
<syntaxhighlight lang="qbasic">#APPTYPE CONSOLE
DIM va[], sign = {1, -1}, toggle
Line 2,823 ⟶ 3,571:
'''Iterative:'''
<syntaxhighlight lang="qbasic">#APPTYPE CONSOLE
DIM va[]
Line 2,858 ⟶ 3,606:
'''Recursive:'''
<syntaxhighlight lang="qbasic">#APPTYPE CONSOLE
DIM va[]
Line 2,887 ⟶ 3,635:
Press any key to continue...</pre>
=={{header|Forth}}==
This version is designed for maintaining a sorted array. If the item is not found, then then location returned is the proper insertion point for the item. This could be used in an optimized [[Insertion sort]], for example.
<syntaxhighlight lang="forth">defer (compare)
' - is (compare) \ default to numbers
Line 2,921 ⟶ 3,668:
11 probe \ -1 11
12 probe \ 0 99</syntaxhighlight>
=={{header|Fortran}}==
'''Recursive'''
In ISO Fortran 90 or later use a RECURSIVE function and ARRAY SECTION argument:
<syntaxhighlight lang="fortran">recursive function binarySearch_R (a, value) result (bsresult)
real, intent(in) :: a(:), value
integer :: bsresult, mid
Line 2,946 ⟶ 3,692:
<br>
In ISO Fortran 90 or later use an ARRAY SECTION POINTER:
<syntaxhighlight lang="fortran">function binarySearch_I (a, value)
integer :: binarySearch_I
real, intent(in), target :: a(:)
Line 2,979 ⟶ 3,725:
The use of "exclusive" bounds simplifies the adjustment of the bounds: the appropriate bound simply receives the value of P, there is ''no'' + 1 or - 1 adjustment ''at every step''; similarly, the determination of an empty span is easy, and avoiding the risk of integer overflow via (L + R)/2 is achieved at the same time. The "inclusive" bounds version by contrast requires ''two'' manipulations of L and R ''at every step'' - once to see if the span is empty, and a second time to locate the index to test.
<syntaxhighlight lang=
Careful: it is surprisingly difficult to make this neat, due to vexations when N = 0 or 1.
REAL X,A(*) !Where is X in array A(1:N)?
Line 3,010 ⟶ 3,756:
====An alternative version====
<syntaxhighlight lang=
Careful: it is surprisingly difficult to make this neat, due to vexations when N = 0 or 1.
REAL X,A(*) !Where is X in array A(1:N)?
Line 3,044 ⟶ 3,790:
Incidentally, the exclusive-bounds version leads to a good version of the interpolation search (whereby the probe position is interpolated, not just in the middle of the span), unlike the version based on inclusive-bounds. Further, the unsourced offering in Wikipedia contains a bug - try searching an array of two equal elements for that value.
=={{header|Futhark}}==
{{incorrect|Futhark|Futhark's syntax has changed, so this example will not compile}}
Line 3,050 ⟶ 3,795:
Straightforward translation of imperative iterative algorithm.
<syntaxhighlight lang=
fun main(as: [n]int, value: int): int =
let low = 0
Line 3,065 ⟶ 3,810:
in low
</syntaxhighlight>
=={{header|GAP}}==
<syntaxhighlight lang="gap">Find := function(v, x)
local low, high, mid;
low := 1;
Line 3,090 ⟶ 3,834:
Find(u, 35);
# 5</syntaxhighlight>
=={{header|Go}}==
'''Recursive''':
<syntaxhighlight lang="go">func binarySearch(a []float64, value float64, low int, high int) int {
if high < low {
return -1
Line 3,106 ⟶ 3,849:
}</syntaxhighlight>
'''Iterative''':
<syntaxhighlight lang="go">func binarySearch(a []float64, value float64) int {
low := 0
high := len(a) - 1
Line 3,122 ⟶ 3,865:
}</syntaxhighlight>
'''Library''':
<syntaxhighlight lang="go">import "sort"
//...
Line 3,130 ⟶ 3,873:
There are also functions <code>sort.SearchFloat64s()</code>, <code>sort.SearchStrings()</code>, and a very general <code>sort.Search()</code> function that allows you to binary search a range of numbers based on any condition (not necessarily just search for an index of an element in an array).
=={{header|Groovy}}==
Both solutions use ''sublists'' and a tracking offset in preference to "high" and "low".
====Recursive Solution====
<syntaxhighlight lang="groovy">
def binSearchR
//define binSearchR closure.
Line 3,151 ⟶ 3,893:
====Iterative Solution====
<syntaxhighlight lang="groovy">def binSearchI = { aList, target ->
def a = aList
def offset = 0
Line 3,169 ⟶ 3,911:
}</syntaxhighlight>
Test:
<syntaxhighlight lang="groovy">def a = [] as Set
def random = new Random()
while (a.size() < 20) { a << random.nextInt(30) }
Line 3,198 ⟶ 3,940:
Trial #5. Looking for: 32
Answer: [insertion point:20], : null</pre>
=={{header|Haskell}}==
===Recursive algorithm===
The algorithm itself, parametrized by an "interrogation" predicate ''p'' in the spirit of the explanation above:
<syntaxhighlight lang="haskell">import Data.Array (Array, Ix, (!), listArray, bounds)
-- BINARY SEARCH --------------------------------------------------------------
Line 3,261 ⟶ 4,002:
A common optimisation of recursion is to delegate the main computation to a helper function with simpler type signature. For the option type of the return value, we could also use an Either as an alternative to a Maybe.
<syntaxhighlight lang="haskell">import Data.Array (Array, Ix, (!), listArray, bounds)
-- BINARY SEARCH USING A HELPER FUNCTION WITH A SIMPLER TYPE SIGNATURE
Line 3,316 ⟶ 4,057:
It returns the result of applying '''f''' until '''p''' holds.
<syntaxhighlight lang="haskell">import Data.Array (Array, Ix, (!), listArray, bounds)
-- BINARY SEARCH USING THE ITERATIVE ALGORITHM
Line 3,368 ⟶ 4,109:
{{Out}}
<pre>'kappa' found at index 7</pre>
=={{header|HicEst}}==
<syntaxhighlight lang="hicest">REAL :: n=10, array(n)
array = NINT( RAN(n) )
Line 3,402 ⟶ 4,142:
ENDDO
END</syntaxhighlight>
<syntaxhighlight lang="hicest">7 has position 9 in 0 0 1 2 3 3 4 6 7 8
5 has position 0 in 0 0 1 2 3 3 4 6 7 8</syntaxhighlight>
=={{header|Hoon}}==
<syntaxhighlight lang="hoon">|= [arr=(list @ud) x=@ud]
=/ lo=@ud 0
=/ hi=@ud (dec (lent arr))
Line 3,416 ⟶ 4,155:
?: (gth x val) $(lo +(mid))
mid</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
Only a recursive solution is shown here.
<syntaxhighlight lang="icon">procedure binsearch(A, target)
if *A = 0 then fail
mid := *A/2 + 1
Line 3,431 ⟶ 4,169:
end</syntaxhighlight>
A program to test this is:
<syntaxhighlight lang="icon">procedure main(args)
target := integer(!args) | 3
every put(A := [], 1 to 18 by 2)
Line 3,475 ⟶ 4,213:
->
</pre>
=={{header|J}}==
J already includes a binary search primitive (<code>I.</code>). The following code offers an interface compatible with the requirement of this task, and returns either the index of the element if it has been found or 'Not Found' otherwise:
<syntaxhighlight lang="j">bs=. i. 'Not Found'"_^:(-.@-:) I.</syntaxhighlight>
'''Examples:'''
<syntaxhighlight lang="j"> 2 3 5 6 8 10 11 15 19 20 bs 11
6
2 3 5 6 8 10 11 15 19 20 bs 12
Line 3,487 ⟶ 4,224:
'''Iterative'''
<syntaxhighlight lang="j">'X Y L H M'=. i.5 NB. Setting mnemonics for boxes
f=. &({::) NB. Fetching the contents of a box
o=. @: NB. Composing verbs (functions)
Line 3,501 ⟶ 4,238:
bs=. return o (squeeze o midpoint ^: (L f <: H f) ^:_) o LowHigh o boxes</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="j">'X Y L H M'=. i.5 NB. Setting mnemonics for boxes
f=. &({::) NB. Fetching the contents of a box
o=. @: NB. Composing verbs (functions)
Line 3,512 ⟶ 4,249:
bs=. (recur o midpoint`('Not Found'"_) @. (H f < L f) o boxes) :: ([ bs ] ; 0 ; (<: o # o [))</syntaxhighlight>
=={{header|Java}}==
'''Iterative'''
<syntaxhighlight lang="java">public class BinarySearchIterative {
public static int binarySearch(int[] nums, int check) {
Line 3,547 ⟶ 4,283:
'''Recursive'''
<syntaxhighlight lang="java">public class BinarySearchRecursive {
public static int binarySearch(int[] haystack, int needle, int lo, int hi) {
Line 3,579 ⟶ 4,315:
For arrays:
<syntaxhighlight lang="java">import java.util.Arrays;
int index = Arrays.binarySearch(array, thing);
Line 3,588 ⟶ 4,324:
int index = Arrays.binarySearch(array, startIndex, endIndex, thing, comparator);</syntaxhighlight>
For Lists:
<syntaxhighlight lang="java">import java.util.Collections;
int index = Collections.binarySearch(list, thing);
int index = Collections.binarySearch(list, thing, comparator);</syntaxhighlight>
=={{header|JavaScript}}==
===ES5===
Recursive binary search implementation
<syntaxhighlight lang="javascript">function binary_search_recursive(a, value, lo, hi) {
if (hi < lo) { return null; }
Line 3,610 ⟶ 4,345:
}</syntaxhighlight>
Iterative binary search implementation
<syntaxhighlight lang="javascript">function binary_search_iterative(a, value) {
var mid, lo = 0,
hi = a.length - 1;
Line 3,632 ⟶ 4,367:
Recursive and iterative, by composition of pure functions, with tests and output:
<syntaxhighlight lang="javascript">(() => {
'use strict';
Line 3,829 ⟶ 4,564:
]
]</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 3,844 ⟶ 4,586:
end;
binarySearch(0; length-1);</syntaxhighlight>
Example:<syntaxhighlight lang="jq">[-1,-1.1,1,1,null,[null]] | binarySearch(1)</syntaxhighlight>
{{Out}}
2
=={{header|Jsish}}==
<syntaxhighlight lang="javascript">/**
Binary search, in Jsish, based on Javascript entry
Tectonics: jsish -u -time true -verbose true binarySearch.jsi
Line 3,912 ⟶ 4,654:
>
[PASS] binarySearch.jsi (165 ms)</pre>
=={{header|Julia}}==
{{works with|Julia|0.6}}
'''Iterative''':
<syntaxhighlight lang="julia">function binarysearch(lst::Vector{T}, val::T) where T
low = 1
high = length(lst)
Line 3,933 ⟶ 4,674:
'''Recursive''':
<syntaxhighlight lang="julia">function binarysearch(lst::Vector{T}, value::T, low=1, high=length(lst)) where T
if isempty(lst) return 0 end
if low ≥ high
Line 3,951 ⟶ 4,692:
end
end</syntaxhighlight>
=={{header|K}}==
Recursive:
<syntaxhighlight lang=
bs:{[a;t]
if[0=#a; :_n];
Line 3,970 ⟶ 4,710:
0 1 2 3 4 5 6 7 8 9
</syntaxhighlight>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">fun <T : Comparable<T>> Array<T>.iterativeBinarySearch(target: T): Int {
var hi = size - 1
var lo = 0
Line 4,015 ⟶ 4,754:
6 found at index 4
250 not found</pre>
=={{header|Lambdatalk}}==
Can be tested in (http://lambdaway.free.fr)[http://lambdaway.free.fr/lambdaway/?view=binary_search]
<syntaxhighlight lang="scheme">
{def BS
{def BS.r {lambda {:a :v :i0 :i1}
Line 4,047 ⟶ 4,785:
{BS {B} 100} -> 100 is not found
{BS {B} 12345} -> 12345 is at array[6172]
</syntaxhighlight>
=={{header|Logo}}==
<syntaxhighlight lang="logo">to bsearch :value :a :lower :upper
if :upper < :lower [output []]
localmake "mid int (:lower + :upper) / 2
Line 4,080 ⟶ 4,795:
output :mid
end</syntaxhighlight>
=={{header|Lolcode}}==
'''Iterative'''
<syntaxhighlight lang="lolcode">
HAI 1.2
CAN HAS STDIO?
Line 4,183 ⟶ 4,897:
I CAN HAS UR CHEEZBURGER NAO?
</pre>
=={{header|Lua}}==
'''Iterative'''
<syntaxhighlight lang="lua">function binarySearch (list,value)
local low = 1
local high = #list
Line 4,199 ⟶ 4,912:
end</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="lua">function binarySearch (list, value)
local function search(low, high)
if low > high then return false end
Line 4,209 ⟶ 4,922:
return search(1,#list)
end</syntaxhighlight>
=={{header|M4}}==
<syntaxhighlight lang="m4">define(`notfound',`-1')dnl
define(`midsearch',`ifelse(defn($1[$4]),$2,$4,
`ifelse(eval(defn($1[$4])>$2),1,`binarysearch($1,$2,$3,decr($4))',`binarysearch($1,$2,incr($4),$5)')')')dnl
define(`binarysearch',`ifelse(eval($4<$3),1,notfound,`midsearch($1,$2,$3,eval(($3+$4)/2),$4)')')dnl
dnl
define(`setrange',`ifelse(`$3',`',$2,`define($1[$2],$3)`'setrange($1,incr($2),shift(shift(shift($@))))')')dnl
define(`asize',decr(setrange(`a',1,1,3,5,7,11,13,17,19,23,29)))dnl
dnl
binarysearch(`a',5,1,asize)
binarysearch(`a',8,1,asize)</syntaxhighlight>
Output:
<pre>
3
-1
</pre>
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang=
\\ binary search
const N=10
Line 4,258 ⟶ 4,986:
</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}}==
Line 4,280 ⟶ 5,052:
'''Recursive'''
<syntaxhighlight lang=
description "recursive binary search";
if high < low then
Line 4,297 ⟶ 5,069:
'''Iterative'''
<syntaxhighlight lang=
description "iterative binary search";
local low, high;
Line 4,315 ⟶ 5,087:
end proc:</syntaxhighlight>
We can use either lists or Arrays (or Vectors) for the first argument for these.
<syntaxhighlight lang=
> P := [seq]( ithprime( i ), i = 1 .. N ):
> BinarySearch( P, 12, 1, N ); # recursive version
Line 4,335 ⟶ 5,107:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
'''Recursive'''
<syntaxhighlight lang=
Module[{mid = lo + Round@((hi - lo)/2)},
If[hi < lo, Return[-1]];
Line 4,345 ⟶ 5,117:
]</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang=
While[lo <= hi,
mid = lo + Round@((hi - lo)/2);
Line 4,355 ⟶ 5,127:
Return[-1];
]</syntaxhighlight>
=={{header|MATLAB}}==
'''Recursive'''
<syntaxhighlight lang=
if( high < low )
Line 4,379 ⟶ 5,150:
end</syntaxhighlight>
Sample Usage:
<syntaxhighlight lang=
ans =
Line 4,385 ⟶ 5,156:
7</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang=
low = 1;
Line 4,406 ⟶ 5,177:
end</syntaxhighlight>
Sample Usage:
<syntaxhighlight lang=
ans =
7</syntaxhighlight>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">find(L, n) := block([i: 1, j: length(L), k, p],
if n < L[i] or n > L[j] then 0 else (
while j - i > 0 do (
Line 4,433 ⟶ 5,203:
find(a, 421);
82</syntaxhighlight>
=={{header|MAXScript}}==
'''Iterative'''
<syntaxhighlight lang="maxscript">fn binarySearchIterative arr value =
(
lower = 1
Line 4,462 ⟶ 5,231:
result = binarySearchIterative arr 6</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="maxscript">fn binarySearchRecursive arr value lower upper =
(
if lower == upper then
Line 4,492 ⟶ 5,261:
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:'''
<syntaxhighlight lang=
if high < low then return null
mid = floor((low + high) / 2)
Line 4,504 ⟶ 5,353:
'''Iterative:'''
<syntaxhighlight lang=
low = 0
high = A.len - 1
Line 4,523 ⟶ 5,372:
{{works with|GNU TROFF|1.22.2}}
<syntaxhighlight lang="text">.de end
..
.de array
Line 4,562 ⟶ 5,411:
.el The item \fBdoes exist\fP.
</syntaxhighlight>
=={{header|Nim}}==
'''Library'''
<syntaxhighlight lang="nim">import algorithm
let s = @[2,3,4,5,6,7,8,9,10,12,14,16,18,20,22,25,27,30]
Line 4,571 ⟶ 5,419:
'''Iterative''' (from the standard library)
<syntaxhighlight lang="nim">proc binarySearch[T](a: openArray[T], key: T): int =
var b = len(a)
while result < b:
Line 4,578 ⟶ 5,426:
else: b = mid
if result >= len(a) or a[result] != key: result = -1</syntaxhighlight>
=={{header|Niue}}==
'''Library'''
<syntaxhighlight lang="ocaml">1 2 3 4 5
3 bsearch . ( => 2 )
5 bsearch . ( => 0 )
Line 4,591 ⟶ 5,438:
'kenny bsearch . ( => 2 )
'tony bsearch . ( => -1)</syntaxhighlight>
=={{header|Oberon-2}}==
{{trans|Pascal}}
<syntaxhighlight lang="oberon2">MODULE BS;
IMPORT Out;
VAR
List:ARRAY 10 OF REAL;
PROCEDURE Init(VAR List:ARRAY OF REAL);
BEGIN
List[0] := -31; List[1] := 0; List[2] := 1; List[3] := 2;
List[4] := 2; List[5] := 4; List[6] := 65; List[7] := 83;
List[8] := 99; List[9] := 782;
END Init;
PROCEDURE BinarySearch(List:ARRAY OF REAL;Element:REAL):LONGINT;
VAR
L,M,H:LONGINT;
BEGIN
L := 0;
H := LEN(List)-1;
WHILE L <= H DO
M := (L + H) DIV 2;
IF List[M] > Element THEN
H := M - 1;
ELSIF List[M] < Element THEN
L := M + 1;
ELSE
RETURN M;
END;
END;
RETURN -1;
END BinarySearch;
PROCEDURE RBinarySearch(VAR List:ARRAY OF REAL;Element:REAL;L,R:LONGINT):LONGINT;
VAR
M:LONGINT;
BEGIN
IF R < L THEN RETURN -1 END;
M := (L + R) DIV 2;
IF Element = List[M] THEN
RETURN M
ELSIF Element < List[M] THEN
RETURN RBinarySearch(List, Element, L, R-1)
ELSE
RETURN RBinarySearch(List, Element, M-1, R)
END;
END RBinarySearch;
BEGIN
Init(List);
Out.Int(BinarySearch(List, 2), 0); Out.Ln;
Out.Int(RBinarySearch(List, 65, 0, LEN(List)-1),0); Out.Ln;
END BS.
</syntaxhighlight>
=={{header|Objeck}}==
'''Iterative'''
<syntaxhighlight lang="objeck">use Structure;
bundle Default {
Line 4,626 ⟶ 5,530:
}
}</syntaxhighlight>
=={{header|Objective-C}}==
'''Iterative'''
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h>
@interface NSArray (BinarySearch)
Line 4,671 ⟶ 5,574:
}</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h>
@interface NSArray (BinarySearchRecursive)
Line 4,711 ⟶ 5,614:
'''Library'''
{{works with|Mac OS X|10.6+}}
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h>
int main()
Line 4,727 ⟶ 5,630:
}</syntaxhighlight>
Using Core Foundation (part of Cocoa, all versions):
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h>
CFComparisonResult myComparator(const void *x, const void *y, void *context) {
Line 4,746 ⟶ 5,649:
return 0;
}</syntaxhighlight>
=={{header|OCaml}}==
'''Recursive'''
<syntaxhighlight lang="ocaml">let rec binary_search a value low high =
if high = low then
if a.(low) = value then
Line 4,772 ⟶ 5,674:
</pre>
OCaml supports proper tail-recursion; so this is effectively the same as iteration.
=={{header|Octave}}==
'''Recursive'''
<syntaxhighlight lang="octave">function i = binsearch_r(array, val, low, high)
if ( high < low )
i = 0;
Line 4,790 ⟶ 5,691:
endfunction</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="octave">function i = binsearch(array, value)
low = 1;
high = numel(array);
Line 4,807 ⟶ 5,708:
endfunction</syntaxhighlight>
'''Example of using'''
<syntaxhighlight lang="octave">r = sort(discrete_rnd(10, [1:10], ones(10,1)/10));
disp(r);
binsearch_r(r, 5, 1, numel(r))
binsearch(r, 5)</syntaxhighlight>
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
(define (binary-search value vector)
(let helper ((low 0)
Line 4,830 ⟶ 5,730:
; ==> 12
</syntaxhighlight>
=={{header|ooRexx}}==
<syntaxhighlight lang=
data = .array~of(1, 3, 5, 7, 9, 11)
-- search keys with a number of edge cases
Line 4,904 ⟶ 5,803:
Key 12 not found
</pre>
=={{header|Oz}}==
'''Recursive'''
<syntaxhighlight lang="oz">declare
fun {BinarySearch Arr Val}
fun {Search Low High}
Line 4,929 ⟶ 5,827:
{System.printInfo "searching 8: "} {Show {BinarySearch A 8}}</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="oz">declare
fun {BinarySearch Arr Val}
Low = {NewCell {Array.low Arr}}
Line 4,948 ⟶ 5,846:
{System.printInfo "searching 4: "} {Show {BinarySearch A 4}}
{System.printInfo "searching 8: "} {Show {BinarySearch A 8}}</syntaxhighlight>
=={{header|PARI/GP}}==
Note that, despite the name, <code>setsearch</code> works on sorted vectors as well as sets.
<syntaxhighlight lang="parigp">setsearch(s, n)</syntaxhighlight>
The following is another implementation that takes a more manual approach. Instead of using an intrinsic function, a general binary search algorithm is implemented using the language alone.
Line 4,957 ⟶ 5,854:
{{trans|N/t/roff}}
<syntaxhighlight lang="parigp">binarysearch(v, x) = {
local(
minm = 1,
Line 4,981 ⟶ 5,878:
print("Item does not exist anywhere.") \
)</syntaxhighlight>
=={{header|Pascal}}==
'''Iterative'''
<syntaxhighlight lang="pascal">function binary_search(element: real; list: array of real): integer;
var
l, m, h: integer;
Line 5,010 ⟶ 5,906:
end;</syntaxhighlight>
Usage:
<syntaxhighlight lang="pascal">var
list: array[0 .. 9] of real;
// ...
indexof := binary_search(123, list);</syntaxhighlight>
=={{header|Perl}}==
'''Iterative'''
<syntaxhighlight lang="perl">sub binary_search {
my ($array_ref, $value, $left, $right) = @_;
while ($left <= $right) {
Line 5,034 ⟶ 5,929:
}</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="perl">sub binary_search {
my ($array_ref, $value, $left, $right) = @_;
return -1 if ($right < $left);
Line 5,048 ⟶ 5,943:
}
}</syntaxhighlight>
=={{header|Phix}}==
Standard autoinclude builtin/bsearch.e, reproduced here (for reference only, don't copy/paste unless you plan to modify and rename it)
<!--<syntaxhighlight lang=
<span style="color: #008080;">global</span> <span style="color: #008080;">function</span> <span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">needle</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">haystack</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
Line 5,076 ⟶ 5,970:
Returns a positive index if found, otherwise the negative index where it would go if inserted now. Example use
<!--<syntaxhighlight lang=
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- -1</span>
Line 5,086 ⟶ 5,980:
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- -4</span>
<!--</syntaxhighlight>-->
=={{header|PHP}}==
'''Iterative'''
<syntaxhighlight lang="php">function binary_search( $array, $secret, $start, $end )
{
do
Line 5,109 ⟶ 6,002:
}</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="php">function binary_search( $array, $secret, $start, $end )
{
$guess = (int)($start + ( ( $end - $start ) / 2 ));
Line 5,124 ⟶ 6,017:
return $guess;
}</syntaxhighlight>
=={{header|Picat}}==
===Iterative===
<syntaxhighlight lang=
A = [2, 4, 6, 8, 9],
TestValues = [2,1,8,10,9,5],
Line 5,185 ⟶ 6,077:
===Recursive version===
<syntaxhighlight lang=
Ret = binary_search_rec(A,Value, 1, A.length).
Line 5,198 ⟶ 6,090:
end,
Mid = Mid1.</syntaxhighlight>
=={{header|PicoLisp}}==
'''Recursive'''
<syntaxhighlight lang=
(unless (=0 Len)
(let (N (inc (/ Len 2)) L (nth Lst N))
Line 5,217 ⟶ 6,108:
-> NIL</pre>
'''Iterative'''
<syntaxhighlight lang=
(use (N L)
(loop
Line 5,235 ⟶ 6,126:
: (iterativeSearch (9) (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9)
-> NIL</pre>
=={{header|PL/I}}==
<syntaxhighlight lang=
search: procedure (A, M) returns (fixed binary);
declare (A(*), M) fixed binary;
Line 5,253 ⟶ 6,143:
return (lbound(A,1)-1);
end search;</syntaxhighlight>
=={{header|Pop11}}==
'''Iterative'''
<syntaxhighlight lang="pop11">define BinarySearch(A, value);
lvars low = 1, high = length(A), mid;
while low <= high do
Line 5,278 ⟶ 6,167:
BinarySearch(A, 8) =></syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="pop11">define BinarySearch(A, value);
define do_it(low, high);
if high < low then
Line 5,294 ⟶ 6,183:
do_it(1, length(A));
enddefine;</syntaxhighlight>
=={{header|PowerShell}}==
<syntaxhighlight lang=
function BinarySearch-Iterative ([int[]]$Array, [int]$Value)
{
Line 5,364 ⟶ 6,252:
}
</syntaxhighlight>
<syntaxhighlight lang=
Show-SearchResult -Array 10, 28, 41, 46, 58, 74, 76, 86, 89, 98 -Search 41 -Function Iterative
Show-SearchResult -Array 10, 28, 41, 46, 58, 74, 76, 86, 89, 98 -Search 99 -Function Iterative
Line 5,377 ⟶ 6,265:
Using BinarySearch-Recursive: 11 not found
</pre>
=={{header|Prolog}}==
Tested with Gnu-Prolog.
<syntaxhighlight lang=
length(List,N), bin_search_inner(Elt,List,1,N,Result).
Line 5,410 ⟶ 6,297:
?- bin_search(5,[1,2,4,8],Result).
Result = -1.</pre>
=={{header|Python}}==
===Python: Iterative===
<syntaxhighlight lang="python">def binary_search(l, value):
low = 0
high = len(l)-1
Line 5,528 ⟶ 6,313:
In addition to a search for a particular word in an AZ-sorted list, for example, we could also perform a binary search for a word of a given '''length''' (in a word-list sorted by rising length), or for a particular value of any other comparable property of items in a suitably sorted list:
<syntaxhighlight lang="python"># findIndexBinary :: (a -> Ordering) -> [a] -> Maybe Int
def findIndexBinary(p):
def isFound(bounds):
Line 5,624 ⟶ 6,409:
===Python: Recursive===
<syntaxhighlight lang="python">def binary_search(l, value, low = 0, high = -1):
if not l: return -1
if(high == -1): high = len(l)-1
Line 5,639 ⟶ 6,424:
This time using the recursive definition:
<syntaxhighlight lang="python"># findIndexBinary_ :: (a -> Ordering) -> [a] -> Maybe Int
def findIndexBinary_(p):
def go(xs):
Line 5,713 ⟶ 6,498:
===Python: Library===
<br>Python's <code>bisect</code> module provides binary search functions
<syntaxhighlight lang="python">index = bisect.bisect_left(list, item) # leftmost insertion point
index = bisect.bisect_right(list, item) # rightmost insertion point
index = bisect.bisect(list, item) # same as bisect_right
Line 5,725 ⟶ 6,510:
Complete binary search function with python's <code>bisect</code> module:
<syntaxhighlight lang="python">from bisect import bisect_left
def binary_search(a, x, lo=0, hi=None): # can't use a to specify default for hi
Line 5,734 ⟶ 6,519:
===Python: Approximate binary search===
Returns the nearest item of list l to value.
<syntaxhighlight lang="python">def binary_search(l, value):
low = 0
high = len(l)-1
Line 5,746 ⟶ 6,531:
return mid
return high if abs(l[high] - value) < abs(l[low] - value) else low</syntaxhighlight>
=={{header|Quackery}}==
Written from pseudocode for rightmost insertion point, iterative.
<syntaxhighlight lang=
[ stack ] is nest.bs ( --> n )
[ stack ] is test.bs ( --> n )
Line 5,794 ⟶ 6,578:
Stack empty.</pre>
=={{header|R}}==
'''Recursive'''
<syntaxhighlight lang=
if ( high < low ) {
return(NULL)
Line 5,811 ⟶ 6,594:
}</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang=
low = 1
high = length(A)
Line 5,827 ⟶ 6,610:
}</syntaxhighlight>
'''Example'''
<syntaxhighlight lang=
IterBinSearch(a, 50)
BinSearch(a, 50, 1, length(a)) # output 50
IterBinSearch(a, 101) # outputs NULL</syntaxhighlight>
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
(define (binary-search x v)
Line 5,853 ⟶ 6,635:
(binary-search 6 #(1 3 4 5 7 8 9 10)) ; gives #f
</pre>
=={{header|Raku}}==
(formerly Perl 6)
With either of the below implementations of <code>binary_search</code>, one could write a function to search any object that does <code>Positional</code> this way:
<syntaxhighlight lang="raku" line>sub search (@a, $x --> Int) {
binary_search { $x cmp @a[$^i] }, 0, @a.end
}</syntaxhighlight>
'''Iterative'''
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang="raku" line>sub binary_search (&p, Int $lo is copy, Int $hi is copy --> Int) {
until $lo > $hi {
my Int $mid = ($lo + $hi) div 2;
Line 5,876 ⟶ 6,657:
{{trans|Haskell}}
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang="raku" line>sub binary_search (&p, Int $lo, Int $hi --> Int) {
$lo <= $hi or fail;
my Int $mid = ($lo + $hi) div 2;
Line 5,890 ⟶ 6,671:
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===
(includes the extra credit)
<syntaxhighlight 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,
Line 5,970 ⟶ 6,783:
619 is in the list, its index is: 53
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
decimals(0)
array = [7, 14, 21, 28, 35, 42, 49, 56, 63, 70]
Line 6,008 ⟶ 6,820:
the value 42 was found at index 6
</pre>
=={{header|Ruby}}==
'''Recursive'''
<syntaxhighlight lang="ruby">class Array
def binary_search(val, low=0, high=(length - 1))
return nil if high < low
Line 6,036 ⟶ 6,847:
end</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="ruby">class Array
def binary_search_iterative(val)
low, high = 0, length - 1
Line 6,074 ⟶ 6,885:
'''Built in'''
Since Ruby 2.0, arrays ship with a binary search method "bsearch":
<syntaxhighlight lang="ruby">haystack = [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]
needles = [0,42,45,24324,99999]
needles.select{|needle| haystack.bsearch{|hay| needle <=> hay} } # => [0, 45, 24324]
</syntaxhighlight>Which is 60% faster than "needles & haystack".
=={{header|Rust}}==
'''Iterative'''
<syntaxhighlight lang="rust">fn binary_search<T:PartialOrd>(v: &[T], searchvalue: T) -> Option<T> {
let mut lower = 0 as usize;
let mut upper = v.len() - 1;
Line 6,120 ⟶ 6,910:
None
}</syntaxhighlight>
=={{header|Scala}}==
'''Recursive'''
<syntaxhighlight lang="scala">def binarySearch[A <% Ordered[A]](a: IndexedSeq[A], v: A) = {
def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {
case _ if high < low => None
Line 6,133 ⟶ 6,922:
}</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="scala">def binarySearch[T](xs: Seq[T], x: T)(implicit ordering: Ordering[T]): Option[Int] = {
var low: Int = 0
var high: Int = xs.size - 1
Line 6,146 ⟶ 6,935:
}</syntaxhighlight>
'''Test'''
<syntaxhighlight lang="scala">def testBinarySearch(n: Int) = {
val odds = 1 to n by 2
val result = (0 to n).flatMap(binarySearch(odds, _))
Line 6,164 ⟶ 6,953:
4 is ordinal of 9
5 is ordinal of 11</pre>
=={{header|Scheme}}==
'''Recursive'''
<syntaxhighlight lang="scheme">(define (binary-search value vector)
(let helper ((low 0)
(high (- (vector-length vector) 1)))
Line 6,187 ⟶ 6,975:
The calls to helper are in tail position, so since Scheme implementations
support proper tail-recursion the computation proces is iterative.
=={{header|Seed7}}==
'''Iterative'''
<syntaxhighlight lang="seed7">const func integer: binarySearchIterative (in array elemType: arr, in elemType: aKey) is func
result
var integer: result is 0;
Line 6,211 ⟶ 6,998:
end func;</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="seed7">const func integer: binarySearch (in array elemType: arr, in elemType: aKey, in integer: low, in integer: high) is func
result
var integer: result is 0;
Line 6,227 ⟶ 7,014:
const func integer: binarySearchRecursive (in array elemType: arr, in elemType: aKey) is
return binarySearch(arr, aKey, 1, length(arr));</syntaxhighlight>
=={{header|SequenceL}}==
'''Recursive'''
<syntaxhighlight lang="sequencel">binarySearch(A(1), value(0), low(0), high(0)) :=
let
mid := low + (high - low) / 2;
Line 6,241 ⟶ 7,027:
else
mid;</syntaxhighlight>
=={{header|Sidef}}==
Iterative:
<syntaxhighlight lang="ruby">func binary_search(a, i) {
var l = 0
Line 6,259 ⟶ 7,044:
}</syntaxhighlight>
Recursive:
<syntaxhighlight lang="ruby">func binary_search(arr, value, low=0, high=arr.end) {
high < low && return -1
var middle = ((high+low) // 2)
Line 6,277 ⟶ 7,062:
Usage:
<syntaxhighlight lang="ruby">say binary_search([34, 42, 55, 778], 55); #=> 2</syntaxhighlight>
=={{header|Simula}}==
<syntaxhighlight lang="simula">BEGIN
Line 6,397 ⟶ 7,181:
</pre>
=={{header|SPARK}}==
SPARK does not allow recursion, so only the iterative solution is provided. This example shows the use of a loop assertion.
Line 6,408 ⟶ 7,191:
The first version has a postcondition that if Found is True the Position value returned is correct. This version also has a number of 'check' annotations. These are inserted to allow the Simplifier to prove all the verification conditions. See [[SPARK_Proof_Process|the SPARK Proof Process]].
<syntaxhighlight lang=
subtype Item_Type is Integer; -- From specs.
Line 6,506 ⟶ 7,289:
end Binary_Searches;</syntaxhighlight>
The second version of the package has a stronger postcondition on Search, which also states that if Found is False then there is no value in Source equal to Item. This postcondition cannot be proved without a precondition that Source is ordered. This version needs four user rules (see [[SPARK_Proof_Process|the SPARK Proof Process]]) to be provided to the Simplifier so that it can prove all the verification conditions.
<syntaxhighlight lang=
subtype Item_Type is Integer; -- From specs.
Line 6,628 ⟶ 7,411:
</pre>
The test program:
<syntaxhighlight lang=
with SPARK_IO;
Line 6,724 ⟶ 7,507:
Searching for 6 in ( 1 2 3 4 5 6 7 8 9): found as #96.
</pre>
=={{header|Standard ML}}==
'''Recursive'''
<syntaxhighlight lang="sml">fun binary_search cmp (key, arr) =
let
fun aux slice =
Line 6,782 ⟶ 7,564:
val it = SOME (4,8) : (int * IntArray.elem) option
</pre>
=={{header|Swift}}==
'''Recursive'''
<syntaxhighlight lang="swift">func binarySearch<T: Comparable>(xs: [T], x: T) -> Int? {
var recurse: ((Int, Int) -> Int?)!
recurse = {(low, high) in switch (low + high) / 2 {
Line 6,796 ⟶ 7,577:
}</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="swift">func binarySearch<T: Comparable>(xs: [T], x: T) -> Int? {
var (low, high) = (0, xs.count - 1)
while low <= high {
Line 6,808 ⟶ 7,589:
}</syntaxhighlight>
'''Test'''
<syntaxhighlight lang="swift">func testBinarySearch(n: Int) {
let odds = Array(stride(from: 1, through: n, by: 2))
let result = flatMap(0...n) {binarySearch(odds, $0)}
Line 6,831 ⟶ 7,612:
4 is ordinal of 9
5 is ordinal of 11</pre>
=={{header|Symsyn}}==
<syntaxhighlight lang="symsyn">
a : 1 : 2 : 27 : 44 : 46 : 57 : 77 : 154 : 212
Line 6,866 ⟶ 7,645:
</syntaxhighlight>
=={{header|Tcl}}==
ref: [http://wiki.tcl.tk/22796 Tcl wiki]
<syntaxhighlight lang="tcl">proc binSrch {lst x} {
set len [llength $lst]
if {$len == 0} {
Line 6,895 ⟶ 7,673:
}</syntaxhighlight>
Note also that, from Tcl 8.4 onwards, the <tt>lsearch</tt> command includes the <tt>-sorted</tt> option to enable binary searching of Tcl lists.
<syntaxhighlight lang="tcl">proc binarySearch {lst x} {
set idx [lsearch -sorted -exact $lst $x]
if {$idx == -1} {
Line 6,903 ⟶ 7,681:
}
}</syntaxhighlight>
=={{header|UNIX Shell}}==
Line 6,960 ⟶ 7,686:
'''Reading values line by line'''
<syntaxhighlight lang="bash">
#!/bin/ksh
# This should work on any clone of Bourne Shell, ksh is the fastest.
Line 6,976 ⟶ 7,702:
'''Iterative'''
<syntaxhighlight lang="bash">
left=0
right=$(($size - 1))
Line 6,995 ⟶ 7,721:
'''Recursive'''
<syntaxhighlight lang="text"> No code yet </syntaxhighlight>
=={{header|UnixPipes}}==
'''Parallel'''
<syntaxhighlight lang="bash">splitter() {
a=$1; s=$2; l=$3; r=$4;
mid=$(expr ${#a[*]} / 2);
Line 7,017 ⟶ 7,742:
echo "1 2 3 4 6 7 8 9" | binsearch 6</syntaxhighlight>
=={{header|Vedit macro language}}==
Line 7,136 ⟶ 7,748:
For this implementation, the numbers to be searched must be stored in current edit buffer, one number per line.
(Could be for example a csv table where the first column is used as key field.)
<syntaxhighlight lang="vedit">// Main program for testing BINARY_SEARCH
#3 = Get_Num("Value to search: ")
EOF
Line 7,167 ⟶ 7,779:
return(0) // not found</syntaxhighlight>
=={{header|
<syntaxhighlight lang="v (vlang)">fn binary_search_rec(a []f64, value f64, low int, high int) int { // recursive
if high <= low {
return -1
Line 7,253 ⟶ 7,826:
=={{header|Wortel}}==
{{trans|JavaScript}}
<syntaxhighlight lang="wortel">; Recursive
@var rec &[a v l h] [
@if < h l @return null
Line 7,277 ⟶ 7,850:
null
]</syntaxhighlight>
=={{header|Wren}}==
<syntaxhighlight lang=
static recursive(a, value, low, high) {
if (high < low) return -1
Line 7,344 ⟶ 7,916:
{{trans|C}}
{{works with|EXPL-32}}
<syntaxhighlight lang="xpl0">
\Binary search
code CrLf=9, IntOut=11, Text=12;
Line 7,410 ⟶ 7,982:
5 is not found.
</pre>
=={{header|z/Arch Assembler}}==
This optimized version for z/Arch, uses six general regs and avoid branch misspredictions for high/low cases.
<syntaxhighlight lang="z/
BINSRCH LA R5,TABLE Begin of table
SR R2,R2 low = 0
Line 7,465 ⟶ 8,002:
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.
<syntaxhighlight lang="zkl">fcn bsearch(list,value){ // list is sorted
fcn(list,value, low,high){
if (high < low) return(Void); // not found
Line 7,477 ⟶ 8,111:
}(list,value,0,list.len()-1);
}</syntaxhighlight>
<syntaxhighlight lang="zkl">list:=T(1,3,5,7,9,11); println("Sorted values: ",list);
foreach i in ([0..12]){
n:=bsearch(list,i);
Line 7,500 ⟶ 8,134:
Not found: 12
</pre>
|