Binary search: Difference between revisions
m
→{{header|Chapel}}
(→Recursive algorithm: Adjusted names and type signatures for easier comparison with Python version) |
LalaithMeren (talk | contribs) |
||
| (114 intermediate revisions by 49 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 20:
;Traditional algorithm
The algorithms are as follows (from [[wp:Binary search algorithm|Wikipedia]]). The algorithms return the index of some element that equals the given value (if there are multiple such elements, it returns some arbitrary one). It is also possible, when the element is not found, to return the "insertion point" for it (the index that the value would have if it were inserted into the array).
'''Recursive Pseudocode''':
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}}==
<
V low = 0
V high = l.len - 1
Line 159 ⟶ 158:
E
R mid
R -1</
=={{header|360 Assembly}}==
<
BINSEAR CSECT
USING BINSEAR,R13 base register
Line 232 ⟶ 230:
XDEC DS CL12 temp
YREGS
END BINSEAR</
{{out}}
<pre>
Line 238 ⟶ 236:
229 found at 23
</pre>
=={{header|8080 Assembly}}==
This is the iterative version of the 'leftmost insertion point' algorithm. (On a processor like the 8080, you would not want to use recursion if you can avoid it. A subroutine call alone takes two bytes of stack space, meaning the needed stack space would be bigger than the array that's being searched.) For simplicity, it operates on an array of unsigned 8-bit integers, as this is the 8080's native datatype, and this task is about binary search, not about implementing operations on other datatypes in terms of 8-bit integers.
On entry, the subroutine <code>binsrch</code> takes the lookup value in the <code>B</code> register, a pointer to the start of the array in the <code>HL</code> registers, and a pointer to the end of the array in the <code>DE</code> registers. On exit, <code>HL</code> will contain the location of the value in the array, if it was found, and the leftmost insertion point, if it was not.
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
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Binary search in array of unsigned 8-bit integers
;; B = value to look for
;; HL = begin of array (low)
;; DE = end of array, inclusive (high)
;; The entry point is 'binsrch'
;; On return, HL = location of value (if contained
;; in array), or insertion point (if not)
binsrch_lo: inx h ; low = mid + 1
inx sp ; throw away 'low'
inx sp
binsrch: mov a,d ; low > high? (are we there yet?)
cmp h ; test high byte
rc
mov a,e ; test low byte
cmp l
rc
push h ; store 'low'
dad d ; mid = (low+high)>>1
mov a,h ; rotate the carry flag back in
rar ; to take care of any overflow
mov h,a
mov a,l
rar
mov l,a
mov a,m ; A[mid] >= value?
cmp b
jc binsrch_lo
xchg ; high = mid - 1
dcx d
pop h ; restore 'low'
jmp binsrch
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Test data
primes: db 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
db 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83
db 89, 97, 101, 103, 107, 109, 113, 127, 131
db 137, 139, 149, 151, 157, 163, 167, 173, 179
db 181, 191, 193, 197, 199, 211, 223, 227, 229
db 233, 239, 241, 251
primes_last: equ $ - 1
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Test code (CP/M compatible)
yep: db ": yes", 13, 10, "$"
nope: db ": no", 13, 10, "$"
num_out: mov a,b ;; Output number in B as decimal
mvi c,100
call dgt_out
mvi c,10
call dgt_out
mvi c,1
dgt_out: mvi e,'0' - 1 ;; Output 100s, 10s or 1s
dgt_out_loop: inr e ;; (depending on C)
sub c
jnc dgt_out_loop
add c
e_out: push psw ;; Output character in E
push b ;; preserving working registers
mvi c,2
call 5
pop b
pop psw
ret
;; Main test code
test: mvi b,0 ; Test value
test_loop: call num_out ; Output current number to test
lxi h,primes ; Set up input for binary search
lxi d,primes_last
call binsrch ; Search for B in array
lxi d,nope ; Location of "no" string
mov a,b ; Check if location binsrch returned
cmp m ; contains the value we were looking for
jnz str_out ; If not, print the "no" string
lxi d,yep ; But if so, use location of "yes" string
str_out: push b ; Preserve B across CP/M call
mvi c,9 ; Print the string
call 5
pop b ; Restore B
inr b ; Test next value
jnz test_loop
rst 0
</syntaxhighlight>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program binSearch64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
sMessResult: .asciz "Value find at index : @ \n"
szCarriageReturn: .asciz "\n"
sMessRecursif: .asciz "Recursive search : \n"
sMessNotFound: .asciz "Value not found. \n"
TableNumber: .quad 4,6,7,10,11,15,22,30,35
.equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
mov x0,4 // search first value
ldr x1,qAdrTableNumber // address number table
mov x2,NBELEMENTS // number of élements
bl bSearch
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
mov x0,#11 // search median value
ldr x1,qAdrTableNumber
mov x2,#NBELEMENTS
bl bSearch
ldr x1,qAdrsZoneConv
bl conversion10 // decimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
mov x0,#12 //value not found
ldr x1,qAdrTableNumber
mov x2,#NBELEMENTS
bl bSearch
cmp x0,#-1
bne 2f
ldr x0,qAdrsMessNotFound
bl affichageMess
b 3f
2:
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
3:
mov x0,#35 // search last value
ldr x1,qAdrTableNumber
mov x2,#NBELEMENTS
bl bSearch
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
/****************************************/
/* recursive */
/****************************************/
ldr x0,qAdrsMessRecursif
bl affichageMess // display message
mov x0,#4 // search first value
ldr x1,qAdrTableNumber
mov x2,#0 // low index of elements
mov x3,#NBELEMENTS - 1 // high index of elements
bl bSearchR
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
mov x0,#11
ldr x1,qAdrTableNumber
mov x2,#0
mov x3,#NBELEMENTS - 1
bl bSearchR
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
mov x0,#12
ldr x1,qAdrTableNumber
mov x2,#0
mov x3,#NBELEMENTS - 1
bl bSearchR
cmp x0,#-1
bne 4f
ldr x0,qAdrsMessNotFound
bl affichageMess
b 5f
4:
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
5:
mov x0,#35
ldr x1,qAdrTableNumber
mov x2,#0
mov x3,#NBELEMENTS - 1
bl bSearchR
ldr x1,qAdrsZoneConv
bl conversion10 // décimal conversion
ldr x0,qAdrsMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc // insert result at @ character
bl affichageMess // display message
100: // standard end of the program
mov x0, #0 // return code
mov x8, #EXIT // request to exit program
svc #0 // perform the system call
//qAdrsMessValeur: .quad sMessValeur
qAdrsZoneConv: .quad sZoneConv
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsMessResult: .quad sMessResult
qAdrsMessRecursif: .quad sMessRecursif
qAdrsMessNotFound: .quad sMessNotFound
qAdrTableNumber: .quad TableNumber
/******************************************************************/
/* binary search iterative */
/******************************************************************/
/* x0 contains the value to search */
/* x1 contains the adress of table */
/* x2 contains the number of elements */
/* x0 return index or -1 if not find */
bSearch:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
mov x3,#0 // low index
sub x4,x2,#1 // high index = number of elements - 1
1:
cmp x3,x4
bgt 99f
add x2,x3,x4 // compute (low + high) /2
lsr x2,x2,#1
ldr x5,[x1,x2,lsl #3] // load value of table at index x2
cmp x5,x0
beq 98f
bgt 2f
add x3,x2,#1 // lower -> index low = index + 1
b 1b // and loop
2:
sub x4,x2,#1 // bigger -> index high = index - 1
b 1b // and loop
98:
mov x0,x2 // find !!!
b 100f
99:
mov x0,#-1 //not found
100:
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* binary search recursif */
/******************************************************************/
/* x0 contains the value to search */
/* x1 contains the adress of table */
/* x2 contains the low index of elements */
/* x3 contains the high index of elements */
/* x0 return index or -1 if not find */
bSearchR:
stp x2,lr,[sp,-16]! // save registers
stp x3,x4,[sp,-16]! // save registers
stp x5,x6,[sp,-16]! // save registers
cmp x3,x2 // index high < low ?
bge 1f
mov x0,#-1 // yes -> not found
b 100f
1:
add x4,x2,x3 // compute (low + high) /2
lsr x4,x4,#1
ldr x5,[x1,x4,lsl #3] // load value of table at index x4
cmp x5,x0
beq 99f
bgt 2f // bigger ?
add x2,x4,#1 // no new search with low = index + 1
bl bSearchR
b 100f
2: // bigger
sub x3,x4,#1 // new search with high = index - 1
bl bSearchR
b 100f
99:
mov x0,x4 // find !!!
b 100f
100:
ldp x5,x6,[sp],16 // restaur 2 registers
ldp x3,x4,[sp],16 // restaur 2 registers
ldp x2,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
Value find at index : 0
Value find at index : 4
Value not found.
Value find at index : 8
Recursive search :
Value find at index : 0
Value find at index : 4
Value not found.
Value find at index : 8
</pre>
=={{header|ACL2}}==
<
(cons name
(compress1 name
Line 301 ⟶ 660:
(populate-array-ordered
(defarray 'haystack *dim* 0)
*dim*)))</
=={{header|Action!}}==
<syntaxhighlight lang="action!">INT FUNC BinarySearch(INT ARRAY a INT len,value)
INT low,high,mid
low=0 high=len-1
WHILE low<=high
DO
mid=low+(high-low) RSH 1
IF a(mid)>value THEN
high=mid-1
ELSEIF a(mid)<value THEN
low=mid+1
ELSE
RETURN (mid)
FI
OD
RETURN (-1)
PROC Test(INT ARRAY a INT len,value)
INT i
Put('[)
FOR i=0 TO len-1
DO
PrintI(a(i))
IF i<len-1 THEN Put(32) FI
OD
i=BinarySearch(a,len,value)
Print("] ") PrintI(value)
IF i<0 THEN
PrintE(" not found")
ELSE
Print(" found at index ")
PrintIE(i)
FI
RETURN
PROC Main()
INT ARRAY a=[65530 0 1 2 5 6 8 9]
Test(a,8,6)
Test(a,8,-6)
Test(a,8,9)
Test(a,8,-10)
Test(a,8,10)
Test(a,8,7)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Binary_search.png Screenshot from Atari 8-bit computer]
<pre>
[-6 0 1 2 5 6 8 9] 6 found at index 5
[-6 0 1 2 5 6 8 9] -6 found at index 0
[-6 0 1 2 5 6 8 9] 9 found at index 7
[-6 0 1 2 5 6 8 9] -10 not found
[-6 0 1 2 5 6 8 9] 10 not found
[-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:
<
procedure Test_Recursive_Binary_Search is
Line 359 ⟶ 774:
Test ((2, 4, 6, 8, 9), 9);
Test ((2, 4, 6, 8, 9), 5);
end Test_Recursive_Binary_Search;</
;Iterative:
<
procedure Test_Binary_Search is
Line 416 ⟶ 831:
Test ((2, 4, 6, 8, 9), 9);
Test ((2, 4, 6, 8, 9), 5);
end Test_Binary_Search;</
Sample output:
<pre>
Line 426 ⟶ 841:
2 4 6 8 9 does not contain 5
</pre>
=={{header|ALGOL 68}}==
<syntaxhighlight lang="algol68">BEGIN
MODE ELEMENT = STRING;
# Iterative: #
PROC iterative binary search = ([]ELEMENT hay stack, ELEMENT needle)INT: (
Line 447 ⟶ 859:
stop iteration:
out
);
# Recursive: #
PROC recursive binary search = ([]ELEMENT hay stack, ELEMENT needle)INT: (
Line 467 ⟶ 879:
[]ELEMENT hay stack = ("AA","Maestro","Mario","Master","Mattress","Mister","Mistress","ZZ"),
test cases = ("A","Master","Monk","ZZZ");
PROC test search = (PROC([]ELEMENT, ELEMENT)INT search, []ELEMENT test cases)VOID:
FOR case TO UPB test cases DO
Line 473 ⟶ 885:
INT index = search(hay stack, needle);
BOOL found = ( index <= 0 | FALSE | hay stack[index]=needle);
OD;
test search(iterative binary search, test cases);
test search(recursive binary search, test cases)
)
END</syntaxhighlight>
{{out}}
Shows iterative search output - recursive search output is the same.
<pre>
"A" near index 1
Line 485 ⟶ 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 ( * )
; integer value find, Low, high
) ;
if high < low then low
else begin
integer mid;
mid := ( low + high ) div 2;
if A( mid ) >= find then binarySearchLR( A, find, low, mid - 1 )
else binarySearchLR( A, find, mid + 1, high )
end binarySearchR ;
% iteratve binary search leftmost insertion point %
integer procedure binarySearchLI ( integer array A ( * )
; integer value find, lowInit, highInit
) ;
begin
integer low, high;
low := lowInit;
high := highInit;
while low <= high do begin
integer mid;
mid := ( low + high ) div 2;
if A( mid ) >= find then high := mid - 1
else low := mid + 1
end while_low_le_high ;
low
end binarySearchLI ;
% tests %
begin
integer array t ( 1 :: 10 );
integer tPos;
tPos := 1;
for tValue := 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 do begin
t( tPos ) := tValue;
tPos := tPOs + 1
end for_tValue ;
for s := 0 step 8 until 24 do begin
integer pos;
pos := binarySearchLR( t, s, 1, 10 );
if t( pos ) = s then write( I_W := 3, S_W := 0, "recursive search finds ", s, " at ", pos )
else write( I_W := 3, S_W := 0, "recursive search suggests insert ", s, " at ", pos )
;
pos := binarySearchLI( t, s, 1, 10 );
if t( pos ) = s then write( I_W := 3, S_W := 0, "iterative search finds ", s, " at ", pos )
else write( I_W := 3, S_W := 0, "iterative search suggests insert ", s, " at ", pos )
end for_s
end
end.</syntaxhighlight>
{{out}}
<pre>
recursive search suggests insert 0 at 1
iterative search suggests insert 0 at 1
recursive search suggests insert 8 at 3
iterative search suggests insert 8 at 3
recursive search finds 16 at 4
iterative search finds 16 at 4
recursive search suggests insert 24 at 5
iterative search suggests insert 24 at 5
</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang="apl">binsrch←{
⎕IO(⍺{ ⍝ first lower bound is start of array
⍵<⍺:⍬ ⍝ if high < low, we didn't find it
mid←⌊(⍺+⍵)÷2 ⍝ calculate mid point
⍺⍺[mid]>⍵⍵:⍺∇mid-1 ⍝ if too high, search from ⍺ to mid-1
⍺⍺[mid]<⍵⍵:(mid+1)∇⍵ ⍝ if too low, search from mid+1 to ⍵
mid ⍝ otherwise, we did find it
}⍵)⎕IO+(≢⍺)-1 ⍝ first higher bound is top of array
}
</syntaxhighlight>
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">on binarySearch(n, theList, l, r)
repeat until (l = r)
set m to (l + r) div 2
if (item m of theList < n) then
set l to m + 1
else
set r to m
end if
end repeat
if (item l of theList is n) then return l
return missing value
end binarySearch
on test(n, theList, l, r)
set |result| to binarySearch(n, theList, l, r)
if (|result| is missing value) then
return (n as text) & " is not in range " & l & " thru " & r & " of the list"
else
return "The first occurrence of " & n & " in range " & l & " thru " & r & " of the list is at index " & |result|
end if
end test
set theList to {1, 2, 3, 3, 5, 7, 7, 8, 9, 10, 11, 12}
return test(7, theList, 4, 11) & linefeed & test(7, theList, 7, 12) & linefeed & test(7, theList, 1, 5)</syntaxhighlight>
{{output}}
(AppleScript indices are 1-based)
<pre>"The first occurrence of 7 in range 4 thru 11 of the list is at index 6
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">
/* ARM assembly Raspberry PI */
/* program binsearch.s */
/************************************/
/* Constantes */
/************************************/
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
/*********************************/
/* Initialized data */
/*********************************/
.data
sMessResult: .ascii "Value find at index : "
sMessValeur: .fill 11, 1, ' ' @ size => 11
szCarriageReturn: .asciz "\n"
sMessRecursif: .asciz "Recursive search : \n"
sMessNotFound: .asciz "Value not found. \n"
.equ NBELEMENTS, 9
TableNumber: .int 4,6,7,10,11,15,22,30,35
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
mov r0,#4 @ search first value
ldr r1,iAdrTableNumber @ address number table
mov r2,#NBELEMENTS @ number of élements
bl bSearch
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
mov r0,#11 @ search median value
ldr r1,iAdrTableNumber
mov r2,#NBELEMENTS
bl bSearch
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
mov r0,#12 @value not found
ldr r1,iAdrTableNumber
mov r2,#NBELEMENTS
bl bSearch
cmp r0,#-1
bne 2f
ldr r0,iAdrsMessNotFound
bl affichageMess
b 3f
2:
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
3:
mov r0,#35 @ search last value
ldr r1,iAdrTableNumber
mov r2,#NBELEMENTS
bl bSearch
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
/****************************************/
/* recursive */
/****************************************/
ldr r0,iAdrsMessRecursif
bl affichageMess @ display message
mov r0,#4 @ search first value
ldr r1,iAdrTableNumber
mov r2,#0 @ low index of elements
mov r3,#NBELEMENTS - 1 @ high index of elements
bl bSearchR
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
mov r0,#11
ldr r1,iAdrTableNumber
mov r2,#0
mov r3,#NBELEMENTS - 1
bl bSearchR
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
mov r0,#12
ldr r1,iAdrTableNumber
mov r2,#0
mov r3,#NBELEMENTS - 1
bl bSearchR
cmp r0,#-1
bne 2f
ldr r0,iAdrsMessNotFound
bl affichageMess
b 3f
2:
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
3:
mov r0,#35
ldr r1,iAdrTableNumber
mov r2,#0
mov r3,#NBELEMENTS - 1
bl bSearchR
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrsMessValeur: .int sMessValeur
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsMessResult: .int sMessResult
iAdrsMessRecursif: .int sMessRecursif
iAdrsMessNotFound: .int sMessNotFound
iAdrTableNumber: .int TableNumber
/******************************************************************/
/* binary search iterative */
/******************************************************************/
/* r0 contains the value to search */
/* r1 contains the adress of table */
/* r2 contains the number of elements */
/* r0 return index or -1 if not find */
bSearch:
push {r2-r5,lr} @ save registers
mov r3,#0 @ low index
sub r4,r2,#1 @ high index = number of elements - 1
1:
cmp r3,r4
movgt r0,#-1 @not found
bgt 100f
add r2,r3,r4 @ compute (low + high) /2
lsr r2,#1
ldr r5,[r1,r2,lsl #2] @ load value of table at index r2
cmp r5,r0
moveq r0,r2 @ find !!!
beq 100f
addlt r3,r2,#1 @ lower -> index low = index + 1
subgt r4,r2,#1 @ bigger -> index high = index - 1
b 1b @ and loop
100:
pop {r2-r5,lr}
bx lr @ return
/******************************************************************/
/* binary search recursif */
/******************************************************************/
/* r0 contains the value to search */
/* r1 contains the adress of table */
/* r2 contains the low index of elements */
/* r3 contains the high index of elements */
/* r0 return index or -1 if not find */
bSearchR:
push {r2-r5,lr} @ save registers
cmp r3,r2 @ index high < low ?
movlt r0,#-1 @ yes -> not found
blt 100f
add r4,r2,r3 @ compute (low + high) /2
lsr r4,#1
ldr r5,[r1,r4,lsl #2] @ load value of table at index r4
cmp r5,r0
moveq r0,r4 @ find !!!
beq 100f
bgt 1f @ bigger ?
add r2,r4,#1 @ no new search with low = index + 1
bl bSearchR
b 100f
1: @ bigger
sub r3,r4,#1 @ new search with high = index - 1
bl bSearchR
100:
pop {r2-r5,lr}
bx lr @ return
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registres
mov r2,#0 @ counter length
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call systeme
pop {r0,r1,r2,r7,lr} @ restaur des 2 registres
bx lr @ return
/******************************************************************/
/* Converting a register to a decimal unsigned */
/******************************************************************/
/* r0 contains value and r1 address area */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes */
.equ LGZONECAL, 10
conversion10:
push {r1-r4,lr} @ save registers
mov r3,r1
mov r2,#LGZONECAL
1: @ start loop
bl divisionpar10U @unsigned r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
cmp r0,#0 @ stop if quotient = 0
subne r2,#1 @ else previous position
bne 1b @ and loop
@ and move digit from left of area
mov r4,#0
2:
ldrb r1,[r3,r2]
strb r1,[r3,r4]
add r2,#1
add r4,#1
cmp r2,#LGZONECAL
ble 2b
@ and move spaces in end on area
mov r0,r4 @ result length
mov r1,#' ' @ space
3:
strb r1,[r3,r4] @ store space in area
add r4,#1 @ next position
cmp r4,#LGZONECAL
ble 3b @ loop if r4 <= area size
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/
/* division par 10 unsigned */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10U:
push {r2,r3,r4, lr}
mov r4,r0 @ save value
//mov r3,#0xCCCD @ r3 <- magic_number lower raspberry 3
//movt r3,#0xCCCC @ r3 <- magic_number higter raspberry 3
ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2,r3,r4,lr}
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">binarySearch: function [arr,val,low,high][
if high < low -> return ø
mid: shr low+high 1
case [val]
when? [< arr\[mid]] -> return binarySearch arr val low mid-1
when? [> arr\[mid]] -> return binarySearch arr val mid+1 high
else -> return mid
]
ary: [
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
]
loop [0 42 45 24324 99999] 'v [
i: binarySearch ary v 0 (size ary)-1
if? not? null? i -> print ["found" v "at index:" i]
else -> print [v "not found"]
]</syntaxhighlight>
{{out}}
<pre>found 0 at index: 0
42 not found
found 45 at index: 10
found 24324 at index: 24
99999 not found</pre>
=={{header|AutoHotkey}}==
<
StringSplit, A, array, `, ; creates associative array
MsgBox % x := BinarySearch(A, 4, 1, A0) ; Recursive
Line 519 ⟶ 1,350:
}
Return not_found
}</
=={{header|AWK}}==
{{works with|Gawk}}
Line 526 ⟶ 1,356:
{{works with|Nawk}}
'''Recursive'''
<
if (right < left) return 0
middle = int((right + left) / 2)
Line 533 ⟶ 1,363:
return binary_search(array, value, left, middle - 1)
return binary_search(array, value, middle + 1, right)
}</
'''Iterative'''
<
while (left <= right) {
middle = int((right + left) / 2)
Line 543 ⟶ 1,373:
}
return 0
}</
=={{header|Axe}}==
'''Iterative'''
Line 550 ⟶ 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.
<
0→L
r₃-1→H
Line 565 ⟶ 1,394:
End
-1
Return</
=={{header|BASIC}}==
Line 571 ⟶ 1,400:
{{works with|FreeBASIC}}
{{works with|RapidQ}}
<
DIM middle AS Integer
Line 587 ⟶ 1,416:
END SELECT
END IF
END FUNCTION</
'''Iterative'''
{{works with|FreeBASIC}}
{{works with|RapidQ}}
<
DIM middle AS Integer
Line 607 ⟶ 1,436:
WEND
binary_search = 0
END FUNCTION</
'''Testing the function'''
The following program can be used to test both recursive and iterative version.
<
DIM idx AS Integer
Line 633 ⟶ 1,462:
search test(), 4
search test(), 8
search test(), 20</
Output:
Value 4 not found
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)
REM Sorted data
DATA -31, 0, 1, 2, 2, 4, 65, 83, 99, 782
FOR I = 0 TO 9
READ A(I)
NEXT I
N = 10
X = 2
GOSUB DoBinarySearch:
GOSUB PrintResult:
X = 5
GOSUB DoBinarySearch:
GOSUB PrintResult:
END
PrintResult:
PRINT X;
IF IndX >= 0 THEN
PRINT " is at index ";
PRINT IndX;
PRINT "."
ELSE
PRINT " is not found."
ENDIF
RETURN
DoBinarySearch:
REM Binary search algorithm
REM N - number of elements
REM X - searched element
REM Result: IndX - index of X
L = 0
H = N - 1
Found = 0
Loop:
IF L > H THEN AfterLoop:
IF Found <> 0 THEN AfterLoop:
REM (L <= H) and (Found = 0)
M = H - L
M = M / 2
M = L + M
REM So, M = L + (H - L) / 2
IF A(M) < X THEN
L = M + 1
ELSE
IF A(M) > X THEN
H = M - 1
ELSE
Found = 1
ENDIF
ENDIF
GOTO Loop:
AfterLoop:
IF Found = 0 THEN
IndX = -1
ELSE
IndX = M
ENDIF
RETURN
</syntaxhighlight>
{{out}}
<pre>
2 is at index 4.
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}}===
<
array%() = 7, 14, 21, 28, 35, 42, 49, 56, 63, 70
Line 662 ⟶ 1,665:
H% /= 2
UNTIL H%=0
IF S%=A%(B%) THEN = B% ELSE = -1</
==={{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
if array(lo) = target then return lo
if array(hi) = target then return hi
while lo + 1 < hi
if array(md) = target then return md
if array(md)<target then lo = md else hi = md
md = (lo + hi)\2
wend
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}}===
<
110 RANDOMIZE
120 NUMERIC ARR(1 TO 20)
Line 691 ⟶ 1,855:
340 LOOP WHILE BO<=UP AND T(K)<>N
350 IF BO<=UP THEN LET SEARCH=K
360 END DEF</
==={{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="basic">
10 REM Binary search
20 LET N = 10
30 FOR I = 1 TO N
40 READ A(I)
50 NEXT I
60 REM Sorted data
70 DATA -31, 0, 1, 2, 2, 4, 65, 83, 99, 782
80 LET X = 2
90 GOSUB 500
100 GOSUB 200
110 LET X = 5
120 GOSUB 500
130 GOSUB 200
140 END
190 REM Print result
200 PRINT X;
210 IF I1 < 0 THEN 240
220 PRINT "is at index"; I1; "."
230 RETURN
240 PRINT "is not found."
250 RETURN
460 REM Binary search algorithm
470 REM N - number of elements
480 REM X - searched element
490 REM Result: I1 - index of X
500 LET L = 0
510 LET H = N-1
520 LET F = 0
530 LET M = L
540 IF L > H THEN 650
550 IF F <> 0 THEN 650
560 LET M = L+INT((H-L)/2)
570 IF A(M) >= X THEN 600
580 LET L = M+1
590 GOTO 540
600 IF A(M) <= X THEN 630
610 LET H = M-1
620 GOTO 540
630 LET F = 1
640 GOTO 540
650 IF F = 0 THEN 680
660 LET I1 = M
670 RETURN
680 LET I1 = -1
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}}===
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}}==
<
@echo off & setlocal enabledelayedexpansion
Line 743 ⟶ 2,467:
echo . binchop required !b! iterations
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⟩;
BS ⟨a, value, low, high⟩:
mid ← ⌊2÷˜low+high
{
high<low ? ¯1;
(mid⊑a)>value ? BS ⟨a, value, low, mid-1⟩;
(mid⊑a)<value ? BS ⟨a, value, mid+1, high⟩;
mid
}
}
•Show BSearch ⟨8‿30‿35‿45‿49‿77‿79‿82‿87‿97, 97⟩</syntaxhighlight>
<syntaxhighlight lang="text">9</syntaxhighlight>
=={{header|Brat}}==
<
true? high < low
{ null }
Line 776 ⟶ 2,518:
null? index
{ p "Not found" }
{ p "Found at index: #{index}" }</
=={{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}}==
<
int bsearch (int *a, int n, int x) {
int i = 0, j = n - 1;
while (i <= j) {
int k =
if (a[k] == x) {
return k;
Line 803 ⟶ 2,567:
return -1;
}
int k =
if (a[k] == x) {
return k;
Line 820 ⟶ 2,584:
int x = 2;
int i = bsearch(a, n, x);
printf("%d is at index %d.\n", x, i);
else
printf("%d is not found.\n", x);
x = 5;
i = bsearch_r(a, x, 0, n - 1);
printf("%d is at index %d.\n", x, i);
else
printf("%d is not found.\n", x);
return 0;
}
</syntaxhighlight>
{{output}}
<pre>
2 is at index 4.
5 is
</pre>
=={{header|C sharp|C#}}==
'''Recursive'''
<
using System;
Line 966 ⟶ 2,674:
}
}
}</
'''Iterative'''
<
using System;
Line 1,040 ⟶ 2,748:
}
}
}</
'''Example'''
<
using System;
Line 1,084 ⟶ 2,792:
#endif
}
}</
'''Output'''
Line 1,120 ⟶ 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) {
return -1;
}
auto mid = (low + high) / 2;
if (value < array[mid]) {
return binsearch(array, low, mid - 1, value);
} else if (value > array[mid]) {
return binsearch(array, mid + 1, high, value);
}
return mid;
}
#include <iostream>
int main()
{
int array[] = {2, 3, 5, 6, 8};
int result1 = binsearch(array, 0, sizeof(array)/sizeof(int), 4),
result2 = binsearch(array, 0, sizeof(array)/sizeof(int), 8);
if (result1 == -1) std::cout << "4 not found!" << std::endl;
else std::cout << "4 found at " << result1 << std::endl;
if (result2 == -1) std::cout << "8 not found!" << std::endl;
else std::cout << "8 found at " << result2 << std::endl;
return 0;
}</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="cpp">template <class T>
int binSearch(const T arr[], int len, T what) {
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > what)
high = mid - 1;
else if (arr[mid] < what)
low = mid + 1;
else
return mid;
}
return -1; // indicate not found
}</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
<
{
var
while (low <= high)
{
var mid = (low + high) / 2;
Line 1,140 ⟶ 2,909:
}
writeln(binsearch([3, 4, 6, 9, 11], 9));</
{{out}}
Line 1,147 ⟶ 2,916:
=={{header|Clojure}}==
'''Recursive'''
<
([coll t]
(bsearch coll 0 (dec (count coll)) t))
Line 1,162 ⟶ 2,931:
; we've found our target
; so return its index
(= mth t) m)))))</
=={{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
% The datatype must support the < and > operators.
binary_search = proc [T: type] (a: array[T], val: T) returns (bool, int)
where T has lt: proctype (T,T) returns (bool),
T has gt: proctype (T,T) returns (bool)
low: int := array[T]$low(a)
high: int := array[T]$high(a)
while low <= high do
mid: int := low + (high - low) / 2
if a[mid] > val then
high := mid - 1
elseif a[mid] < val then
low := mid + 1
else
return (true, mid)
end
end
return (false, low)
end binary_search
% Test the binary search on an array
start_up = proc ()
po: stream := stream$primary_output()
% primes up to 20 (note that arrays are 1-indexed by default)
primes: array[int] := array[int]$[2,3,5,7,11,13,17,19]
% binary search for each number from 1 to 20
for n: int in int$from_to(1,20) do
i: int
found: bool
found, i := binary_search[int](primes, n)
if found then
stream$putl(po, int$unparse(n)
|| " found at location "
|| int$unparse(i));
else
stream$putl(po, int$unparse(n)
|| " not found, would be inserted at location "
|| int$unparse(i));
end
end
end start_up</syntaxhighlight>
{{out}}
<pre>1 not found, would be inserted at location 1
2 found at location 1
3 found at location 2
4 not found, would be inserted at location 3
5 found at location 3
6 not found, would be inserted at location 4
7 found at location 4
8 not found, would be inserted at location 5
9 not found, would be inserted at location 5
10 not found, would be inserted at location 5
11 found at location 5
12 not found, would be inserted at location 6
13 found at location 6
14 not found, would be inserted at location 7
15 not found, would be inserted at location 7
16 not found, would be inserted at location 7
17 found at location 7
18 not found, would be inserted at location 8
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.
<
IDENTIFICATION DIVISION.
PROGRAM-ID. binary-search.
Line 1,183 ⟶ 3,020:
END-SEARCH
.
END PROGRAM binary-search.</
=={{header|CoffeeScript}}==
'''Recursive'''
<
do recurse = (low = 0, high = xs.length - 1) ->
mid = Math.floor (low + high) / 2
Line 1,194 ⟶ 3,030:
when xs[mid] > x then recurse low, mid - 1
when xs[mid] < x then recurse mid + 1, high
else mid</
'''Iterative'''
<
[low, high] = [0, xs.length - 1]
while low <= high
Line 1,204 ⟶ 3,040:
when xs[mid] < x then low = mid + 1
else return mid
NaN</
'''Test'''
<
odds = (it for it in [1..n] by 2)
result = (it for it in \
Line 1,213 ⟶ 3,049:
console.assert "#{result}" is "#{[0...odds.length]}"
console.log "#{odds} are odd natural numbers"
console.log "#{it} is ordinal of #{odds[it]}" for it in result</
Output:
<pre>1,3,5,7,9,11 are odd natural numbers"
Line 1,222 ⟶ 3,058:
4 is ordinal of 9
5 is ordinal of 11</pre>
=={{header|Common Lisp}}==
'''Iterative'''
<
(let ((low 0)
(high (1- (length array))))
Line 1,238 ⟶ 3,073:
(setf low (1+ middle)))
(t (return middle)))))))</
'''Recursive'''
<
(if (< high low)
nil
Line 1,251 ⟶ 3,086:
(binary-search value array (1+ middle) high))
(t middle)))))</
=={{header|Crystal}}==
'''Recursive'''
<syntaxhighlight lang="ruby">class Array
def binary_search(val, low = 0, high = (size - 1))
return nil if high < low
#mid = (low + high) >> 1
mid = low + ((high - low) >> 1)
case val <=> self[mid]
when -1
binary_search(val, low, mid - 1)
when 1
binary_search(val, mid + 1, high)
else mid
end
end
end
ary = [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]
[0, 42, 45, 24324, 99999].each do |val|
i = ary.binary_search(val)
if i
puts "found #{val} at index #{i}: #{ary[i]}"
else
puts "#{val} not found in array"
end
end</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="ruby">class Array
def binary_search_iterative(val)
low, high = 0, size - 1
while low <= high
#mid = (low + high) >> 1
mid = low + ((high - low) >> 1)
case val <=> self[mid]
when 1
low = mid + 1
when -1
high = mid - 1
else
return mid
end
end
nil
end
end
ary = [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]
[0, 42, 45, 24324, 99999].each do |val|
i = ary.binary_search_iterative(val)
if i
puts "found #{val} at index #{i}: #{ary[i]}"
else
puts "#{val} not found in array"
end
end</syntaxhighlight>
{{out}}
<pre>
found 0 at index 0: 0
42 not found in array
found 45 at index 10: 45
found 24324 at index 24: 24324
99999 not found in array
</pre>
=={{header|D}}==
<
/// Recursive.
Line 1,294 ⟶ 3,193:
// Standard Binary Search:
!items.equalRange(x).empty);
}</
{{out}}
<pre> 1 false false false
Line 1,302 ⟶ 3,201:
5 false false false
2 true true true</pre>
=={{header|Delphi}}==
See [[#Pascal]].
=={{header|E}}==
<
def binarySearch(collection, value) {
var low := 0
Line 1,317 ⟶ 3,217:
}
return null
}</
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
proc binSearch val . a[] res .
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 ]
binSearch 8 a[] r
print r
</syntaxhighlight>
=={{header|Eiffel}}==
Line 1,323 ⟶ 3,244:
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.
<
APPLICATION
Line 1,442 ⟶ 3,363:
end
end</
=={{header|Elixir}}==
<
def search(list, value), do: search(List.to_tuple(list), value, 0, length(list)-1)
Line 1,466 ⟶ 3,386:
index -> IO.puts "found #{val} at index #{index}"
end
end)</
{{out}}
Line 1,477 ⟶ 3,397:
</pre>
=={{header|Emacs Lisp}}==
<
(let ((low 0)
(high (1- (length array))))
(cl-do () ((< high low) nil)
(let ((middle (floor (+ low high) 2)))
(cond ((> (aref array middle) value)
(setf high (1- middle)))
((< (aref array middle) value)
(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}}==
<
%% Author: Abhay Jain
Line 1,520 ⟶ 3,485:
Mid
end
end.</
=={{header|Euphoria}}==
===Recursive===
<
integer mid, cmp
if high < low then
Line 1,539 ⟶ 3,503:
end if
end if
end function</
===Iterative===
<
integer low, high, mid, cmp
low = 1
Line 1,557 ⟶ 3,521:
end while
return 0 -- not found
end function</
=={{header|F Sharp|F#}}==
Generic recursive version, using #light syntax:
<
if (high < low) then
null
Line 1,572 ⟶ 3,535:
binarySearch (myArray, mid+1, high, value)
else
myArray.[mid]</
=={{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:
<
DIM va[], sign = {1, -1}, toggle
Line 1,597 ⟶ 3,565:
" in ", GetTickCount() - gtc, " milliseconds"
PAUSE</
Output:<pre>Loading ... done in 906 milliseconds
Sorting ... done in 547 milliseconds
Line 1,606 ⟶ 3,574:
'''Iterative:'''
<
DIM va[]
Line 1,634 ⟶ 3,602:
WEND
RETURN -1
END FUNCTION</
Output:<pre>Loading ... done in 391 milliseconds
3141592.65358979 found at index 1000000 in 62 milliseconds
Line 1,641 ⟶ 3,609:
'''Recursive:'''
<
DIM va[]
Line 1,665 ⟶ 3,633:
END IF
RETURN midp
END FUNCTION</
Output:<pre>Loading ... done in 390 milliseconds
3141592.65358979 found at index 1000000 in 938 milliseconds
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.
<
' - is (compare) \ default to numbers
Line 1,710 ⟶ 3,670:
10 probe \ 0 11
11 probe \ -1 11
12 probe \ 0 99</
=={{header|Fortran}}==
'''Recursive'''
In ISO Fortran 90 or later use a RECURSIVE function and ARRAY SECTION argument:
<
real, intent(in) :: a(:), value
integer :: bsresult, mid
Line 1,732 ⟶ 3,691:
bsresult = mid ! SUCCESS!!
end if
end function binarySearch_R</
'''Iterative'''
<br>
In ISO Fortran 90 or later use an ARRAY SECTION POINTER:
<
integer :: binarySearch_I
real, intent(in), target :: a(:)
Line 1,758 ⟶ 3,717:
end if
end do
end function binarySearch_I</
===Iterative, exclusive bounds, three-way test.===
Line 1,769 ⟶ 3,728:
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.
<
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 1,788 ⟶ 3,747:
Curse it!
5 FINDI = -L !X is not found. Insert it at L + 1, i.e. at A(1 - FINDI).
END FUNCTION FINDI !A's values need not be all different, merely in order. </
[[File:BinarySearch.Flowchart.png]]
Line 1,800 ⟶ 3,759:
====An alternative version====
<
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 1,819 ⟶ 3,778:
Curse it!
5 FINDI = -L !X is not found. Insert it at L + 1, i.e. at A(1 - FINDI).
END FUNCTION FINDI !A's values need not be all different, merely in order. </
The point of this is that the IF-test is going to initiate some jumps, so why not arrange that one of the bound adjustments needs no subsequent jump to the start of the next iteration - in the first version, both bound adjustments needed such a jump, the GO TO 1 statements. This was done by shifting the code for label 2 up to precede the code for label 1 - and removing its now pointless GO TO 1 (executed each time), but adding an initial GO TO 1, executed once only. This sort of change is routine when manipulating spaghetti code...
Line 1,834 ⟶ 3,793:
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}}
Straightforward translation of imperative iterative algorithm.
<syntaxhighlight lang="futhark">
fun main(as: [n]int, value: int): int =
let low = 0
Line 1,853 ⟶ 3,812:
else (mid, mid-1) -- Force termination.
in low
</syntaxhighlight>
=={{header|GAP}}==
<
local low, high, mid;
low := 1;
Line 1,878 ⟶ 3,836:
# fail
Find(u, 35);
# 5</
=={{header|Go}}==
'''Recursive''':
<
if high < low {
return -1
Line 1,893 ⟶ 3,850:
}
return mid
}</
'''Iterative''':
<
low := 0
high := len(a) - 1
Line 1,909 ⟶ 3,866:
}
return -1
}</
'''Library''':
<
//...
sort.SearchInts([]int{0,1,4,5,6,7,8,9}, 6) // evaluates to 4</
Exploration of library source code shows that it uses the <tt>mid = low + (high - low) / 2</tt> technique to avoid overflow.
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====
<
def binSearchR
//define binSearchR closure.
Line 1,937 ⟶ 3,893:
: [index: offset + m]
}
</syntaxhighlight>
====Iterative Solution====
<
def a = aList
def offset = 0
Line 1,956 ⟶ 3,912:
}
return ["insertion point": offset]
}</
Test:
<
def random = new Random()
while (a.size() < 20) { a << random.nextInt(30) }
Line 1,974 ⟶ 3,930:
println """
Answer: ${answers[0]}, : ${source[answers[0].values().iterator().next()]}"""
}</
Output:
<pre>[1, 2, 5, 8, 9, 10, 11, 14, 15, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 29]
Line 1,987 ⟶ 3,943:
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:
<
-- BINARY SEARCH --------------------------------------------------------------
Line 2,043 ⟶ 3,998:
case found of
Nothing -> "' Not found"
Just x -> "' found at index " ++ show x</
{{Out}}
<pre>'mu' found at index 9</pre>
Line 2,050 ⟶ 4,005:
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.
<
-- BINARY SEARCH USING A HELPER FUNCTION WITH A SIMPLER TYPE SIGNATURE
Line 2,068 ⟶ 4,023:
-- TEST ---------------------------------------------------
haystack =
listArray
(0, 11)
Line 2,088 ⟶ 4,043:
main :: IO ()
main =
let
in putStrLn $
needle ++
either
("' " ++)
(("' found at index " ++) . show)
(findIndexBinary (compare needle) haystack)</syntaxhighlight>
{{Out}}
<pre>'lambda' found at index 8</pre>
===Iterative algorithm===
Line 2,099 ⟶ 4,060:
It returns the result of applying '''f''' until '''p''' holds.
<
--
findIndexBinary_
::
=>
findIndexBinary_ p axs =
let (lo, hi) =
until
Line 2,116 ⟶ 4,072:
(\(lo, hi) ->
let m = quot (lo + hi) 2
in case p (axs ! m) of
LT -> (lo, pred m)
GT -> (succ m, hi)
EQ -> (m, 0))
(
in if 0 /= hi
then Left "not found"
Line 2,126 ⟶ 4,082:
-- TEST ---------------------------------------------------
haystack :: Array Int String
haystack =
listArray
Line 2,148 ⟶ 4,102:
main :: IO ()
main =
let needle = "
in putStrLn $
'\'' :
needle ++
(findIndexBinary_ (compare needle) haystack)</syntaxhighlight>
{{Out}}
<pre>'
=={{header|HicEst}}==
<
array = NINT( RAN(n) )
Line 2,191 ⟶ 4,144:
ENDIF
ENDDO
END</
<
5 has position 0 in 0 0 1 2 3 3 4 6 7 8</
=={{header|Hoon}}==
<syntaxhighlight lang="hoon">|= [arr=(list @ud) x=@ud]
=/ lo=@ud 0
=/ hi=@ud (dec (lent arr))
|-
?> (lte lo hi)
=/ mid (div (add lo hi) 2)
=/ val (snag mid arr)
?: (lth x val) $(hi (dec mid))
?: (gth x val) $(lo +(mid))
mid</syntaxhighlight>
=={{header|Icon}} and {{header|Unicon}}==
Only a recursive solution is shown here.
<
if *A = 0 then fail
mid := *A/2 + 1
Line 2,207 ⟶ 4,170:
}
return mid
end</
A program to test this is:
<
target := integer(!args) | 3
every put(A := [], 1 to 18 by 2)
Line 2,221 ⟶ 4,184:
every writes(!A," ")
write()
end</
with some sample runs:
<pre>
Line 2,253 ⟶ 4,216:
->
</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:
<
'''Examples:'''
<
6
2 3 5 6 8 10 11 15 19 20 bs 12
Not Found</
Direct tacit iterative and recursive versions to compare to other implementations follow:
'''Iterative'''
<
f=. &({::) NB. Fetching the contents of a box
o=. @: NB. Composing verbs (functions)
Line 2,277 ⟶ 4,239:
return=. (M f) o ((<@:('Not Found'"_) M} ]) ^: (_ ~: L f))
bs=. return o (squeeze o midpoint ^: (L f <: H f) ^:_) o LowHigh o boxes</
'''Recursive'''
<
f=. &({::) NB. Fetching the contents of a box
o=. @: NB. Composing verbs (functions)
Line 2,289 ⟶ 4,251:
recur=. (X f bs Y f ; L f ; (_1 + M f))`(M f)`(X f bs Y f ; (1 + M f) ; H f)@.case
bs=. (recur o midpoint`('Not Found'"_) @. (H f < L f) o boxes) :: ([ bs ] ; 0 ; (<: o # o [))</
=={{header|Java}}==
'''Iterative'''
<
public static int binarySearch(int[] nums, int check) {
Line 2,321 ⟶ 4,282:
}
}
}</
'''Recursive'''
<
public static int binarySearch(int[] haystack, int needle, int lo, int hi) {
Line 2,352 ⟶ 4,313:
}
}
}</
'''Library'''
When the key is not found, the following functions return <code>~insertionPoint</code> (the bitwise complement of the index where the key would be inserted, which is guaranteed to be a negative number).
For arrays:
<
int index = Arrays.binarySearch(array, thing);
Line 2,364 ⟶ 4,325:
// for objects, also optionally accepts an additional comparator argument:
int index = Arrays.binarySearch(array, thing, comparator);
int index = Arrays.binarySearch(array, startIndex, endIndex, thing, comparator);</
For Lists:
<
int index = Collections.binarySearch(list, thing);
int index = Collections.binarySearch(list, thing, comparator);</
=={{header|JavaScript}}==
===ES5===
Recursive binary search implementation
<
if (hi < lo) { return null; }
Line 2,386 ⟶ 4,346:
}
return mid;
}</
Iterative binary search implementation
<
var mid, lo = 0,
hi = a.length - 1;
Line 2,404 ⟶ 4,364:
}
return null;
}</
===ES6===
Line 2,410 ⟶ 4,370:
Recursive and iterative, by composition of pure functions, with tests and output:
<
'use strict';
Line 2,566 ⟶ 4,526:
// MAIN ---
return main();
})();</
{{Out}}
<pre>[
Line 2,607 ⟶ 4,567:
]
]</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 2,621 ⟶ 4,588:
end
end;
binarySearch(0; length-1);</
Example:<
{{Out}}
2
=={{header|Jsish}}==
<
Binary search, in Jsish, based on Javascript entry
Tectonics: jsish -u -time true -verbose true binarySearch.jsi
Line 2,679 ⟶ 4,646:
puts('Iterative:', Util.times(function() { binarySearchIterative(arr, 42); }, 100), 'µs');
puts('Recursive:', Util.times(function() { binarySearchRecursive(arr, 42, 0, arr.length - 1); }, 100), 'µs');
}</
{{out}}
Line 2,690 ⟶ 4,657:
>
[PASS] binarySearch.jsi (165 ms)</pre>
=={{header|Julia}}==
{{works with|Julia|0.6}}
'''Iterative''':
<
low = 1
high = length(lst)
Line 2,708 ⟶ 4,674:
end
return 0
end</
'''Recursive''':
<
if isempty(lst) return 0 end
if low ≥ high
Line 2,728 ⟶ 4,694:
return mid
end
end</
=={{header|K}}==
Recursive:
<syntaxhighlight lang="k">
bs:{[a;t]
if[0=#a; :_n];
Line 2,747 ⟶ 4,712:
{bs[v;x]}' v
0 1 2 3 4 5 6 7 8 9
</syntaxhighlight>
=={{header|Kotlin}}==
<
var hi = size - 1
var lo = 0
Line 2,787 ⟶ 4,751:
r = a.recursiveBinarySearch(target, 0, a.size)
println(if (r < 0) "$target not found" else "$target found at index $r")
}</
{{Out}}
<pre>6 found at index 4
Line 2,793 ⟶ 4,757:
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]
<
{def BS
{def BS.r {lambda {:a :v :i0 :i1}
Line 2,825 ⟶ 4,788:
{BS {B} 100} -> 100 is not found
{BS {B} 12345} -> 12345 is at array[6172]
</syntaxhighlight>
=={{header|Logo}}==
<
if :upper < :lower [output []]
localmake "mid int (:lower + :upper) / 2
Line 2,857 ⟶ 4,797:
if item :mid :a < :value [output bsearch :value :a :mid+1 :upper]
output :mid
end</
=={{header|Lolcode}}==
'''Iterative'''
<syntaxhighlight lang="lolcode">
HAI 1.2
CAN HAS STDIO?
VISIBLE "HAI WORLD!!!1!"
VISIBLE "IMA GONNA SHOW U BINA POUNCE NAO"
I HAS A list ITZ A BUKKIT
list HAS A index0 ITZ 2
list HAS A index1 ITZ 3
list HAS A index2 ITZ 5
list HAS A index3 ITZ 7
list HAS A index4 ITZ 8
list HAS A index5 ITZ 9
list HAS A index6 ITZ 12
list HAS A index7 ITZ 20
BTW Method to access list by index number aka: list[index4]
HOW IZ list access YR indexNameNumber
FOUND YR list'Z SRS indexNameNumber
IF U SAY SO
BTW Method to print the array on the same line
HOW IZ list printList
I HAS A allList ITZ ""
I HAS A indexNameNumber ITZ "index0"
I HAS A index ITZ 0
IM IN YR walkingLoop UPPIN YR index TIL BOTH SAEM index AN 8
indexNameNumber R SMOOSH "index" index MKAY
allList R SMOOSH allList " " list IZ access YR indexNameNumber MKAY MKAY
IM OUTTA YR walkingLoop
FOUND YR allList
IF U SAY SO
VISIBLE "WE START WIF BUKKIT LIEK DIS: " list IZ printList MKAY
I HAS A target ITZ 12
VISIBLE "AN TARGET LIEK DIS: " target
VISIBLE "AN NAO 4 MAGI"
HOW IZ I binaPounce YR list AN YR listLength AN YR target
I HAS A left ITZ 0
I HAS A right ITZ DIFF OF listLength AN 1
IM IN YR whileLoop
BTW exit while loop when left > right
DIFFRINT left AN SMALLR OF left AN right
O RLY?
YA RLY
GTFO
OIC
I HAS A mid ITZ QUOSHUNT OF SUM OF left AN right AN 2
I HAS A midIndexname ITZ SMOOSH "index" mid MKAY
BTW if target == list[mid] return mid
BOTH SAEM target AN list IZ access YR midIndexname MKAY
O RLY?
YA RLY
FOUND YR mid
OIC
BTW if target < list[mid] right = mid - 1
DIFFRINT target AN BIGGR OF target AN list IZ access YR midIndexname MKAY
O RLY?
YA RLY
right R DIFF OF mid AN 1
OIC
BTW if target > list[mid] left = mid + 1
DIFFRINT target AN SMALLR OF target AN list IZ access YR midIndexname MKAY
O RLY?
YA RLY
left R SUM OF mid AN 1
OIC
IM OUTTA YR whileLoop
FOUND YR -1
IF U SAY SO
BTW call binary search on target here and print the index
I HAS A targetIndex ITZ I IZ binaPounce YR list AN YR 8 AN YR target MKAY
VISIBLE "TARGET " target " IZ IN BUKKIT " targetIndex
VISIBLE "WE HAS TEH TARGET!!1!!"
VISIBLE "I CAN HAS UR CHEEZBURGER NAO?"
KTHXBYE
end</syntaxhighlight>
Output
<pre>
HAI WORLD!!!1!
IMA GONNA SHOW U BINA POUNCE NAO
WE START WIF BUKKIT LIEK DIS: 2 3 5 7 8 9 12 20
AN TARGET LIEK DIS: 12
AN NAO 4 MAGI
TARGET 12 IZ IN BUKKIT 6
WE HAS TEH TARGET!!1!!
I CAN HAS UR CHEEZBURGER NAO?
</pre>
=={{header|Lua}}==
'''Iterative'''
<
local low = 1
local high = #list
Line 2,872 ⟶ 4,913:
end
return false
end</
'''Recursive'''
<
local function search(low, high)
if low > high then return false end
Line 2,883 ⟶ 4,924:
end
return search(1,#list)
end</
=={{header|M4}}==
<
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
Line 2,895 ⟶ 4,935:
dnl
binarysearch(`a',5,1,asize)
binarysearch(`a',8,1,asize)</
Output:
<pre>
Line 2,901 ⟶ 4,941:
-1
</pre>
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
\\ binary search
const N=10
Dim A(0 to N-1)
A(0):=1,2,3,4,5,6,8,9,10,11
Print Len(A())=10
Function BinarySearch(&A(), aValue) {
def long mid, lo, hi
def boolean ok=False
let lo=0, hi=Len(A())-1
While lo<=hi
mid=(lo+hi)/2
if A(mid)>aValue Then
hi=mid-1
Else.if A(mid)<aValue Then
lo=mid+1
Else
=mid
ok=True
exit
End if
End While
if not ok then =-lo-1
}
For i=0 to 12
Rem Print "Search for value:";i
where= BinarySearch(&A(), i)
if where>=0 then
Print "found i at index: ";where
else
where=-where-1
if where<len(A()) then
Print "Not found, we can insert it at index: ";where
Dim A(len(A())+1) ' redim
stock A(where) keep len(A())-where-1, A(where+1) 'move items up
A(where)=i ' insert value
Else
Print "Not found, we can append to array at index: ";where
Dim A(len(A())+1) ' redim
A(where)=i ' insert value
End If
end if
next i
Print Len(A())=13
Print A()
</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 2,906 ⟶ 5,055:
'''Recursive'''
<
description "recursive binary search";
if high < low then
Line 2,920 ⟶ 5,069:
end if
end if
end proc:</
'''Iterative'''
<
description "iterative binary search";
local low, high;
Line 2,939 ⟶ 5,088:
end do;
FAIL
end proc:</
We can use either lists or Arrays (or Vectors) for the first argument for these.
<
> P := [seq]( ithprime( i ), i = 1 .. N ):
> BinarySearch( P, 12, 1, N ); # recursive version
Line 2,957 ⟶ 5,106:
> PP[ 3 ];
13</
=={{header|Mathematica}} / {{header|Wolfram Language}}==
'''Recursive'''
<
Module[{mid = lo + Round@((hi - lo)/2)},
If[hi < lo, Return[-1]];
Line 2,970 ⟶ 5,118:
True, mid]
];
]</
'''Iterative'''
<
While[lo <= hi,
mid = lo + Round@((hi - lo)/2);
Line 2,981 ⟶ 5,129:
];
Return[-1];
]</
=={{header|MATLAB}}==
'''Recursive'''
<
if( high < low )
Line 3,004 ⟶ 5,151:
end
end</
Sample Usage:
<
ans =
7</
'''Iterative'''
<
low = 1;
Line 3,031 ⟶ 5,178:
mid = [];
end</
Sample Usage:
<
ans =
7</
=={{header|Maxima}}==
<
if n < L[i] or n > L[j] then 0 else (
while j - i > 0 do (
Line 3,059 ⟶ 5,205:
0
find(a, 421);
82</
=={{header|MAXScript}}==
'''Iterative'''
<
(
lower = 1
Line 3,087 ⟶ 5,232:
arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10)
result = binarySearchIterative arr 6</
'''Recursive'''
<
(
if lower == upper then
Line 3,118 ⟶ 5,263:
arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10)
result = binarySearchRecursive arr 6 1 arr.count</
=={{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="miniscript">binarySearch = function(A, value, low, high)
if high < low then return null
mid = floor((low + high) / 2)
if A[mid] > value then return binarySearch(A, value, low, mid-1)
if A[mid] < value then return binarySearch(A, value, mid+1, high)
return mid
end function</syntaxhighlight>
'''Iterative:'''
<syntaxhighlight lang="miniscript">binarySearch = function(A, value)
low = 0
high = A.len - 1
while true
if high < low then return null
mid = floor((low + high) / 2)
if A[mid] > value then
high = mid - 1
else if A[mid] < value then
low = mid + 1
else
return mid
end if
end while
end function</syntaxhighlight>
=={{header|N/t/roff}}==
{{works with|GNU TROFF|1.22.2}}
<syntaxhighlight lang="text">.de end
..
.de array
Line 3,161 ⟶ 5,413:
.ie \n[guess]=0 The item \fBdoesn't exist\fP.
.el The item \fBdoes exist\fP.
</syntaxhighlight>
=={{header|Nim}}==
'''Library'''
<
let s = @[2,3,4,5,6,7,8,9,10,12,14,16,18,20,22,25,27,30]
echo binarySearch(s, 10)</
'''Iterative''' (from the standard library)
<
var b = len(a)
while result < b:
Line 3,177 ⟶ 5,428:
if a[mid] < key: result = mid + 1
else: b = mid
if result >= len(a) or a[result] != key: result = -1</
=={{header|Niue}}==
'''Library'''
<
3 bsearch . ( => 2 )
5 bsearch . ( => 0 )
Line 3,190 ⟶ 5,440:
'tom bsearch . ( => 0 )
'kenny bsearch . ( => 2 )
'tony bsearch . ( => -1)</
=={{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'''
<
bundle Default {
Line 3,225 ⟶ 5,532:
}
}
}</
=={{header|Objective-C}}==
'''Iterative'''
<
@interface NSArray (BinarySearch)
Line 3,269 ⟶ 5,575:
}
return 0;
}</
'''Recursive'''
<
@interface NSArray (BinarySearchRecursive)
Line 3,308 ⟶ 5,614:
}
return 0;
}</
'''Library'''
{{works with|Mac OS X|10.6+}}
<
int main()
Line 3,325 ⟶ 5,631:
}
return 0;
}</
Using Core Foundation (part of Cocoa, all versions):
<
CFComparisonResult myComparator(const void *x, const void *y, void *context) {
Line 3,345 ⟶ 5,651:
}
return 0;
}</
=={{header|OCaml}}==
'''Recursive'''
<
if high = low then
if a.(low) = value then
Line 3,361 ⟶ 5,666:
binary_search a value (mid + 1) high
else
mid</
Output:
<pre>
Line 3,372 ⟶ 5,677:
</pre>
OCaml supports proper tail-recursion; so this is effectively the same as iteration.
=={{header|Octave}}==
'''Recursive'''
<
if ( high < low )
i = 0;
Line 3,388 ⟶ 5,692:
endif
endif
endfunction</
'''Iterative'''
<
low = 1;
high = numel(array);
Line 3,405 ⟶ 5,709:
endif
endwhile
endfunction</
'''Example of using'''
<
disp(r);
binsearch_r(r, 5, 1, numel(r))
binsearch(r, 5)</
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
(define (binary-search value vector)
(let helper ((low 0)
(high (- (vector-length vector) 1)))
(unless (< high low)
(let ((middle (quotient (+ low high) 2)))
(cond
((> (vector-ref vector middle) value)
(helper low (- middle 1)))
((< (vector-ref vector middle) value)
(helper (+ middle 1) high))
(else middle))))))
(print
(binary-search 12 [1 2 3 4 5 6 7 8 9 10 11 12 13]))
; ==> 12
</syntaxhighlight>
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
data = .array~of(1, 3, 5, 7, 9, 11)
-- search keys with a number of edge cases
Line 3,466 ⟶ 5,787:
end
return 0
</syntaxhighlight>
Output:
<pre>
Line 3,485 ⟶ 5,806:
Key 12 not found
</pre>
=={{header|Oz}}==
'''Recursive'''
<
fun {BinarySearch Arr Val}
fun {Search Low High}
Line 3,508 ⟶ 5,828:
in
{System.printInfo "searching 4: "} {Show {BinarySearch A 4}}
{System.printInfo "searching 8: "} {Show {BinarySearch A 8}}</
'''Iterative'''
<
fun {BinarySearch Arr Val}
Low = {NewCell {Array.low Arr}}
Line 3,528 ⟶ 5,848:
in
{System.printInfo "searching 4: "} {Show {BinarySearch A 4}}
{System.printInfo "searching 8: "} {Show {BinarySearch A 8}}</
=={{header|PARI/GP}}==
Note that, despite the name, <code>setsearch</code> works on sorted vectors as well as sets.
<syntaxhighlight lang
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 3,538 ⟶ 5,857:
{{trans|N/t/roff}}
<
local(
minm = 1,
Line 3,561 ⟶ 5,880:
print("Item exists on index ", idx), \
print("Item does not exist anywhere.") \
)</
=={{header|Pascal}}==
'''Iterative'''
<
var
l, m, h: integer;
Line 3,589 ⟶ 5,907:
end;
end;
end;</
Usage:
<
list: array[0 .. 9] of real;
// ...
indexof := binary_search(123, list);</
=={{header|Perl}}==
'''Iterative'''
<
my ($array_ref, $value, $left, $right) = @_;
while ($left <= $right) {
Line 3,613 ⟶ 5,930:
}
return -1;
}</
'''Recursive'''
<
my ($array_ref, $value, $left, $right) = @_;
return -1 if ($right < $left);
Line 3,628 ⟶ 5,945:
binary_search($array_ref, $value, $middle + 1, $right);
}
}</
=={{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="phix">-->
<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>
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">haystack</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">hi</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">+</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">needle</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">haystack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color:
<span style="color: #008080;">return</span> <span style="color: #000000;">mid</span> <span style="color: #000080;font-style:italic;">-- found!</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">mid</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">mid</span> <span style="color: #000080;font-style:italic;">-- where it would go, if inserted now</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</syntaxhighlight>-->
The low + (high-low)/2 trick is not needed, since interim integer results are accurate to 53 bits (on 32 bit, 64 bits on 64 bit) on Phix.
Returns a positive index if found, otherwise the negative index where it would go if inserted now. Example use
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</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>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</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;">-- -2</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</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;">-- 2</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</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;">-- -3</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</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;">-- 3</span>
<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'''
<
{
do
Line 3,714 ⟶ 6,003:
return $guess;
}</
'''Recursive'''
<
{
$guess = (int)($start + ( ( $end - $start ) / 2 ));
Line 3,730 ⟶ 6,019:
return $guess;
}</
=={{header|Picat}}==
===Iterative===
<syntaxhighlight lang="picat">go =>
A = [2, 4, 6, 8, 9],
TestValues = [2,1,8,10,9,5],
foreach(Value in TestValues)
test(binary_search,A, Value)
end,
test(binary_search,[1,20,3,4], 5),
nl.
% Test with binary search predicate Search
test(Search,A,Value) =>
Ret = apply(Search,A,Value),
printf("A: %w Value:%d Ret: %d: ", A, Value, Ret),
if Ret == -1 then
println("The array is not sorted.")
elseif Ret == 0 then
printf("The value %d is not in the array.\n", Value)
else
printf("The value %d is found at position %d.\n", Value, Ret)
end.
binary_search(A, Value) = V =>
V1 = 0,
% we want a sorted array
if not sort(A) == A then
V1 := -1
else
Low = 1,
High = A.length,
Mid = 1,
Found = 0,
while (Found == 0, Low <= High)
Mid := (Low + High) // 2,
if A[Mid] > Value then
High := Mid - 1
elseif A[Mid] < Value then
Low := Mid + 1
else
V1 := Mid,
Found := 1
end
end
end,
V = V1.
</syntaxhighlight>
{{out}}
<pre>A: [2,4,6,8,9] Value:2 Ret: 1: The value 2 is found at position 1.
A: [2,4,6,8,9] Value:1 Ret: 0: The value 1 is not in the array.
A: [2,4,6,8,9] Value:8 Ret: 4: The value 8 is found at position 4.
A: [2,4,6,8,9] Value:10 Ret: 0: The value 10 is not in the array.
A: [2,4,6,8,9] Value:9 Ret: 5: The value 9 is found at position 5.
A: [2,4,6,8,9] Value:5 Ret: 0: The value 5 is not in the array.
A: [1,20,3,4] Value:5 Ret: -1: The array is not sorted.
</pre>
===Recursive version===
<syntaxhighlight lang="picat">binary_search_rec(A, Value) = Ret =>
Ret = binary_search_rec(A,Value, 1, A.length).
binary_search_rec(A, _Value, _Low, _High) = -1, sort(A) != A => true.
binary_search_rec(_A, _Value, Low, High) = 0, High < Low => true.
binary_search_rec(A, Value, Low, High) = Mid =>
Mid1 = (Low + High) // 2,
if A[Mid1] > Value then
Mid1 := binary_search_rec(A, Value, Low, Mid1-1)
elseif A[Mid1] < Value then
Mid1 := binary_search_rec(A, Value, Mid1+1, High)
end,
Mid = Mid1.</syntaxhighlight>
=={{header|PicoLisp}}==
'''Recursive'''
<
(unless (=0 Len)
(let (N (inc (/ Len 2)) L (nth Lst N))
Line 3,741 ⟶ 6,102:
((> Val (car L))
(recursiveSearch Val (cdr L) (- Len N)) )
(T (recursiveSearch Val Lst (dec N))) ) ) ) )</
Output:
<pre>: (recursiveSearch 5 (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9)
Line 3,750 ⟶ 6,111:
-> NIL</pre>
'''Iterative'''
<
(use (N L)
(loop
Line 3,760 ⟶ 6,121:
(if (> Val (car L))
(setq Lst (cdr L) Len (- Len N))
(setq Len (dec N)) ) ) ) )</
Output:
<pre>: (iterativeSearch 5 (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9)
Line 3,768 ⟶ 6,129:
: (iterativeSearch (9) (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9)
-> NIL</pre>
=={{header|PL/I}}==
<
search: procedure (A, M) returns (fixed binary);
declare (A(*), M) fixed binary;
Line 3,785 ⟶ 6,145:
end;
return (lbound(A,1)-1);
end search;</
=={{header|Pop11}}==
'''Iterative'''
<
lvars low = 1, high = length(A), mid;
while low <= high do
Line 3,809 ⟶ 6,168:
BinarySearch(A, 4) =>
BinarySearch(A, 5) =>
BinarySearch(A, 8) =></
'''Recursive'''
<
define do_it(low, high);
if high < low then
Line 3,826 ⟶ 6,185:
enddefine;
do_it(1, length(A));
enddefine;</
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function BinarySearch-Iterative ([int[]]$Array, [int]$Value)
{
Line 3,896 ⟶ 6,254:
}
}
</syntaxhighlight>
<syntaxhighlight lang="powershell">
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
Show-SearchResult -Array 10, 28, 41, 46, 58, 74, 76, 86, 89, 98 -Search 86 -Function Recursive
Show-SearchResult -Array 10, 28, 41, 46, 58, 74, 76, 86, 89, 98 -Search 11 -Function Recursive
</syntaxhighlight>
{{Out}}
<pre>
Line 3,910 ⟶ 6,268:
Using BinarySearch-Recursive: 11 not found
</pre>
=={{header|Prolog}}==
Tested with Gnu-Prolog.
<
length(List,N), bin_search_inner(Elt,List,1,N,Result).
Line 3,935 ⟶ 6,292:
MidElt > Elt,
NewEnd is Mid-1,
bin_search_inner(Elt,List,Begin,NewEnd,Result).</
{{out|Output examples}}
Line 3,944 ⟶ 6,301:
Result = -1.</pre>
=={{header|
===Python: Iterative===
<syntaxhighlight lang="python">def binary_search(l, value):
low = 0
high = len(l)-1
while low <= high:
mid = (low+high)//2
if l[mid] > value: high = mid-1
elif l[mid] < value: low = mid+1
else: return mid
return -1</syntaxhighlight>
We can also generalize this kind of binary search from direct matches to searches using a custom comparator function.
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):
(lo, hi) = bounds
def half(xs):
def choice(lh):
(lo, hi) = lh
mid = (lo + hi) // 2
cmpr = p(xs[mid])
return (lo, mid - 1) if cmpr < 0 else (
(1 + mid, hi) if cmpr > 0 else (
mid, 0
)
)
return lambda bounds: choice(bounds)
def go(xs):
(lo, hi) = until(isFound)(
half(xs)
)((0, len(xs) - 1)) if xs else None
return None if 0 != hi else lo
return lambda xs: go(xs)
# COMPARISON CONSTRUCTORS ---------------------------------
# compare :: a -> a -> Ordering
def compare(a):
'''Simple comparison of x and y -> LT|EQ|GT'''
return lambda b: -1 if a < b else (1 if a > b else 0)
# byKV :: (a -> b) -> a -> a -> Ordering
def byKV(f):
'''Property accessor function -> target value -> x -> LT|EQ|GT'''
def go(v, x):
fx = f(x)
return -1 if v < fx else 1 if v > fx else 0
return lambda v: lambda x: go(v, x)
# TESTS ---------------------------------------------------
def main():
# BINARY SEARCH FOR WORD IN AZ-SORTED LIST
mb1 = findIndexBinary(compare('iota'))(
# Sorted AZ
['alpha', 'beta', 'delta', 'epsilon', 'eta', 'gamma', 'iota',
'kappa', 'lambda', 'mu', 'theta', 'zeta']
)
print (
'Not found' if None is mb1 else (
'Word found at index ' + str(mb1)
# BINARY SEARCH FOR WORD OF GIVEN LENGTH (IN WORD-LENGTH SORTED LIST)
mb2 = findIndexBinary(byKV(len)(7))(
['mu', 'eta', 'beta', 'iota', 'zeta', 'alpha', 'delta', 'gamma',
'kappa', 'theta', 'lambda', 'epsilon']
)
print (
'Not found' if None is mb2 else (
'Word of given length found at index ' + str(mb2)
)
)
# GENERIC -------------------------------------------------
# until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
def go(f, x):
v = x
while not p(v):
v = f(v)
return v
return lambda f: lambda x: go(f, x)
if __name__ == '__main__':
main()
</syntaxhighlight>
{{Out}}
<pre>Word found at index 6
Word of given length found at index 11</pre>
===Python: Recursive===
<
if not l: return -1
if(high == -1): high = len(l)-1
Line 4,068 ⟶ 6,421:
if l[mid] > value: return binary_search(l, value, low, mid-1)
elif l[mid] < value: return binary_search(l, value, mid+1, high)
else: return mid</
Generalizing again with a custom comparator function (see preamble to second iterative version above).
This time using the recursive definition:
<syntaxhighlight lang="python"># findIndexBinary_ :: (a -> Ordering) -> [a] -> Maybe Int
def findIndexBinary_(p):
def go(xs):
def bin(lo, hi):
Line 4,116 ⟶ 6,470:
# BINARY SEARCH FOR WORD IN AZ-SORTED LIST
mb1 =
# Sorted AZ
['alpha', 'beta', 'delta', 'epsilon', 'eta', 'gamma', 'iota',
Line 4,130 ⟶ 6,484:
# BINARY SEARCH FOR WORD OF GIVEN LENGTH (IN WORD-LENGTH SORTED LIST)
mb2 =
# Sorted by rising length
['mu', 'eta', 'beta', 'iota', 'zeta', 'alpha', 'delta', 'gamma',
Line 4,140 ⟶ 6,494:
'Word of given length found at index ' + str(mb2)
)
)</
{{Out}}
<pre>Word found at index 9
Line 4,147 ⟶ 6,501:
===Python: Library===
<br>Python's <code>bisect</code> module provides binary search functions
<
index = bisect.bisect_right(list, item) # rightmost insertion point
index = bisect.bisect(list, item) # same as bisect_right
Line 4,154 ⟶ 6,508:
bisect.insort_left(list, item)
bisect.insort_right(list, item)
bisect.insort(list, item)</
====Python: Alternate====
Complete binary search function with python's <code>bisect</code> module:
<
def binary_search(a, x, lo=0, hi=None): # can't use a to specify default for hi
hi = hi if hi is not None else len(a) # hi defaults to len(a)
pos = bisect_left(a,x,lo,hi) # find insertion position
return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end</
===Python: Approximate binary search===
Returns the nearest item of list l to value.
<
low = 0
high = len(l)-1
Line 4,179 ⟶ 6,533:
else:
return mid
return high if abs(l[high] - value) < abs(l[low] - value) else low</
=={{header|Quackery}}==
Written from pseudocode for rightmost insertion point, iterative.
<syntaxhighlight lang="quackery"> [ stack ] is value.bs ( --> n )
[ stack ] is nest.bs ( --> n )
[ stack ] is test.bs ( --> n )
[ ]'[ test.bs put
value.bs put
nest.bs put
1 - swap
[ 2dup < if done
2dup + 1 >>
nest.bs share over peek
value.bs share swap
test.bs share do iff
[ 1 - unrot nip ]
again
[ 1+ nip ] again ]
drop
nest.bs take over peek
value.bs take 2dup swap
test.bs share do
dip [ test.bs take do ]
or not
dup dip [ not + ] ] is bsearchwith ( n n [ x --> n b )
[ dup echo
over size 0 swap 2swap
bsearchwith < iff
[ say " was identified as item " ]
else
[ say " could go into position " ]
echo
say "." cr ] is task ( [ n --> n )</syntaxhighlight>
{{out}}
Testing in the shell.
<pre>/O> ' [ 10 20 30 40 50 60 70 80 90 ] 30 task
... ' [ 10 20 30 40 50 60 70 80 90 ] 66 task
...
30 was identified as item 2.
66 could go into position 6.
Stack empty.</pre>
=={{header|R}}==
'''Recursive'''
<
if ( high < low ) {
return(NULL)
Line 4,195 ⟶ 6,595:
mid
}
}</
'''Iterative'''
<
low = 1
high = length(A)
Line 4,211 ⟶ 6,611:
}
NULL
}</
'''Example'''
<
IterBinSearch(a, 50)
BinSearch(a, 50, 1, length(a)) # output 50
IterBinSearch(a, 101) # outputs NULL</
=={{header|Racket}}==
<
#lang racket
(define (binary-search x v)
Line 4,233 ⟶ 6,632:
[else m])]))
(loop 0 (vector-length v)))
</syntaxhighlight>
Examples:
<pre>
Line 4,239 ⟶ 6,638:
(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;
given p $mid {
when -1 { $hi = $mid - 1; }
when 1 { $lo = $mid + 1; }
default { return $mid; }
}
}
fail;
}</syntaxhighlight>
'''Recursive'''
{{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;
given p $mid {
when -1 { binary_search &p, $lo, $mid - 1 }
when 1 { binary_search &p, $mid + 1, $hi }
default { $mid }
}
}</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"></syntaxhighlight>
/*REXX program finds a value in a list of integers using an iterative binary search.*/
list=3 7
743 761 773 797 811 823 829 839 859 863 883 887 911 919 941 953 971 983 1013
/* [needle] a list of some low weak primes.*/
Parse Arg needle . /* get a # that's specified on t*/
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
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)
<
@= 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
/* [↑]
parse arg ? . /*get a
if ?=='' then do; say; say '***error*** no argument specified.'; say
end
low
high
say 'arithmetic mean of the ' high " values
say
do while low<=high; mid= (low + high) % 2; y= word(@, mid)
if ?=y then
exit /*stick a fork in it, we're all done. */
end
if y>? then high= mid - 1 /*too high? */
else low= mid + 1 /*too low? */
end /*while*/
say ? " wasn't found in the list." /*stick a fork in it, we're all done. */</syntaxhighlight>
{{out|output|text= when using the input of: <tt> -314 </tt>}}
<pre>
arithmetic mean of the 79 values
-314 wasn't found in the list.
</pre>
<pre>
arithmetic mean of the 79 values
619 is in the list, its index is: 53
</pre>
=={{header|Ring}}==
<
decimals(0)
array = [7, 14, 21, 28, 35, 42, 49, 56, 63, 70]
find= 42
index = where(array,
if index >= 0
see "the value " + find+ " was found at index " + index
Line 4,342 ⟶ 6,799:
ok
func where
h = 2
while h<(t-b)
h *= 2
end
h /= 2
while h != 0
if (b+h)<=t
if s>=a[b+h]
b += h
ok
ok
h /= 2
end
if s=a[b]
return b-1
else
return -1
ok
</syntaxhighlight>
Output:
<pre>
the value 42 was found at index 6
</pre>
=={{header|Ruby}}==
'''Recursive'''
<
def binary_search(val, low=0, high=(length - 1))
return nil if high < low
Line 4,382 ⟶ 6,848:
puts "#{val} not found in array"
end
end</
'''Iterative'''
<
def binary_search_iterative(val)
low, high = 0, length - 1
while low <= high
mid = (low + high) >> 1
case
when 1
low = mid + 1
Line 4,411 ⟶ 6,877:
puts "#{val} not found in array"
end
end</
{{out}}
<pre>
Line 4,422 ⟶ 6,888:
'''Built in'''
Since Ruby 2.0, arrays ship with a binary search method "bsearch":
<
needles = [0,42,45,24324,99999]
needles.select{|needle| haystack.bsearch{|hay| needle <=> hay} } # => [0, 45, 24324]
</
=={{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;
while
} else if searchvalue
} else
}
}
None
}</syntaxhighlight>
=={{header|Scala}}==
'''Recursive'''
<
def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {
case _ if high < low => None
Line 4,485 ⟶ 6,923:
}
recurse(0, a.size - 1)
}</
'''Iterative'''
<
var low: Int = 0
var high: Int = xs.size - 1
Line 4,498 ⟶ 6,936:
}
None //not found
}</
'''Test'''
<
val odds = 1 to n by 2
val result = (0 to n).flatMap(binarySearch(odds, _))
Line 4,509 ⟶ 6,947:
}
def main() = testBinarySearch(12)</
Output:
<pre>Range(1, 3, 5, 7, 9, 11) are odd natural numbers
Line 4,518 ⟶ 6,956:
4 is ordinal of 9
5 is ordinal of 11</pre>
=={{header|Scheme}}==
'''Recursive'''
<
(let helper ((low 0)
(high (- (vector-length vector) 1)))
Line 4,531 ⟶ 6,968:
((< (vector-ref vector middle) value)
(helper (+ middle 1) high))
(else middle))))))</
Example:
<pre>
Line 4,541 ⟶ 6,978:
The calls to helper are in tail position, so since Scheme implementations
support proper tail-recursion the computation proces is iterative.
=={{header|Seed7}}==
'''Iterative'''
<
result
var integer: result is 0;
Line 4,563 ⟶ 6,999:
end if;
end while;
end func;</
'''Recursive'''
<
result
var integer: result is 0;
Line 4,580 ⟶ 7,016:
const func integer: binarySearchRecursive (in array elemType: arr, in elemType: aKey) is
return binarySearch(arr, aKey, 1, length(arr));</
=={{header|SequenceL}}==
'''Recursive'''
<
let
mid := low + (high - low) / 2;
Line 4,594 ⟶ 7,029:
binarySearch(A, value, mid + 1, high) when A[mid] < value
else
mid;</
=={{header|Sidef}}==
Iterative:
<
var l = 0
Line 4,611 ⟶ 7,045:
return -1
}</
Recursive:
<
high < low && return -1
var middle = ((high+low) // 2)
Line 4,628 ⟶ 7,062:
}
}
}</
Usage:
<
=={{header|Simula}}==
<
Line 4,720 ⟶ 7,154:
END;
END</
{{out}}
<pre>
Line 4,750 ⟶ 7,184:
</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 4,802 ⟶ 7,194:
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]].
<
subtype Item_Type is Integer; -- From specs.
Line 4,898 ⟶ 7,290:
end Search;
end Binary_Searches;</
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.
<
subtype Item_Type is Integer; -- From specs.
Line 4,989 ⟶ 7,381:
end Search;
end Binary_Searches;</
The user rules for this version of the package (written in FDL, a language for modelling algorithms).
<pre>binary_search_rule(1): (X + Y) div 2 >= X
Line 5,022 ⟶ 7,414:
</pre>
The test program:
<
with SPARK_IO;
Line 5,106 ⟶ 7,498:
Run_Search (Source => Array_Type9'(1, 2, 3, 4, 5, 6, 7, 8, 9), Item => 6);
end Test_Binary_Search;
</syntaxhighlight>
Test output (for the last three tests the array is indexed from 91):
Line 5,118 ⟶ 7,510:
Searching for 6 in ( 1 2 3 4 5 6 7 8 9): found as #96.
</pre>
=={{header|Standard ML}}==
'''Recursive'''
<
let
fun aux slice =
Line 5,137 ⟶ 7,528:
in
aux (ArraySlice.full arr)
end</
Usage:
<pre>
Line 5,176 ⟶ 7,567:
val it = SOME (4,8) : (int * IntArray.elem) option
</pre>
=={{header|Swift}}==
'''Recursive'''
<
var recurse: ((Int, Int) -> Int?)!
recurse = {(low, high) in switch (low + high) / 2 {
Line 5,188 ⟶ 7,578:
}}
return recurse(0, xs.count - 1)
}</
'''Iterative'''
<
var (low, high) = (0, xs.count - 1)
while low <= high {
Line 5,200 ⟶ 7,590:
}
return nil
}</
'''Test'''
<
let odds = Array(stride(from: 1, through: n, by: 2))
let result = flatMap(0...n) {binarySearch(odds, $0)}
Line 5,216 ⟶ 7,606:
func flatMap<T, U>(source: [T], transform: (T) -> U?) -> [U] {
return source.reduce([]) {(var xs, x) in if let x = transform(x) {xs.append(x)}; return xs}
}</
Output:
<pre>[1, 3, 5, 7, 9, 11] are odd natural numbers
Line 5,225 ⟶ 7,615:
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
binary_search param item index size
index saveindex
index L
(index + size - 1) H
if L <= H
((L + H) shr 1) M
if base.M > item
- 1 M H
else
if base.M < item
+ 1 M L
else
- saveindex M
return M
endif
endif
goif
endif
return -1
start
call binary_search 77 @a #a
result R
"'result = ' R" []
</syntaxhighlight>
=={{header|Tcl}}==
ref: [http://wiki.tcl.tk/22796 Tcl wiki]
<
set len [llength $lst]
if {$len == 0} {
Line 5,252 ⟶ 7,674:
puts "element $x found at index $idx"
}
}</
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.
<
set idx [lsearch -sorted -exact $lst $x]
if {$idx == -1} {
Line 5,261 ⟶ 7,683:
puts "element $x found at index $idx"
}
}</
=={{header|
'''Reading values line by line'''
<syntaxhighlight lang="bash">
#!/bin/ksh
# This should work on any clone of Bourne Shell, ksh is the fastest.
value=$1; [ -z "$value" ] && exit
array=()
size=0
while IFS= read -r line; do
size=$(($size + 1))
array[${#array[*]}]=$line
done
</syntaxhighlight>
'''Iterative'''
<syntaxhighlight lang="bash">
left=0
right=$(($size - 1))
while [ $left -le $right ] ; do
mid=$((($left + $right) >> 1))
# echo "$left $mid(${array[$mid]}) $right"
if [ $value -eq ${array[$mid]} ] ; then
echo $mid
exit
elif [ $value -lt ${array[$mid]} ]; then
right=$(($mid - 1))
else
left=$((mid + 1))
fi
done
echo 'ERROR 404 : NOT FOUND'
</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang="text"> No code yet </syntaxhighlight>
=={{header|UnixPipes}}==
'''Parallel'''
<
a=$1; s=$2; l=$3; r=$4;
mid=$(expr ${#a[*]} / 2);
Line 5,334 ⟶ 7,744:
}
echo "1 2 3 4 6 7 8 9" | binsearch 6</
=={{header|Vedit macro language}}==
Line 5,411 ⟶ 7,751:
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.)
<
#3 = Get_Num("Value to search: ")
EOF
Line 5,440 ⟶ 7,780:
}
}
return(0) // not found</
=={{header|
<syntaxhighlight lang="v (vlang)">fn binary_search_rec(a []f64, value f64, low int, high int) int { // recursive
if high <= low {
}
if a[mid] > value {
return binary_search_rec(a, value, low, mid-1)
} else if a[mid] < value {
return binary_search_rec(a, value, mid+1, high)
}
return mid
}
fn binary_search_it(a []f64, value f64) int { //iterative
mut low := 0
mut high := a.len - 1
for low <= high {
mid := (low + high) / 2
if a[mid] > value {
high = mid - 1
} else if a[mid] < value {
low = mid + 1
} else {
return mid
}
}
return -1
}
fn main() {
f_list := [1.2,1.5,2,5,5.13,5.4,5.89,9,10]
println(binary_search_rec(f_list,9,0,f_list.len))
println(binary_search_rec(f_list,15,0,f_list.len))
println(binary_search_it(f_list,9))
println(binary_search_it(f_list,15))
}</syntaxhighlight>
{{out}}
<pre>
7
-1
7
-1
</pre>
=={{header|Wortel}}==
{{trans|JavaScript}}
<
@var rec &[a v l h] [
@if < h l @return null
Line 5,549 ⟶ 7,852:
]
null
]</
=={{header|Wren}}==
<syntaxhighlight lang="wren">class BinarySearch {
static recursive(a, value, low, high) {
if (high < low) return -1
var mid = low + ((high - low)/2).floor
if (a[mid] > value) return recursive(a, value, low, mid-1)
if (a[mid] < value) return recursive(a, value, mid+1, high)
return mid
}
static iterative(a, value) {
var low = 0
var high = a.count - 1
var mid = low + ((high - low)/2).floor
if (a[mid] > value) {
high = mid - 1
} else if (a[mid] < value) {
low = mid + 1
} else {
return mid
}
}
return -1
}
}
var a = [10, 22, 45, 67, 89, 97]
System.print("array = %(a)")
System.print("\nUsing the recursive algorithm:")
for (value in [67, 93]) {
var index = BinarySearch.recursive(a, value, 0, a.count - 1)
if (index >= 0) {
System.print(" %(value) was found at index %(index) of the array.")
} else {
System.print(" %(value) was not found in the array.")
}
}
System.print("\nUsing the iterative algorithm:")
for (value in [22, 70]) {
var index = BinarySearch.iterative(a, value)
if (index >= 0) {
System.print(" %(value) was found at index %(index) of the array.")
} else {
System.print(" %(value) was not found in the array.")
}
}</syntaxhighlight>
{{out}}
<pre>
array = [10, 22, 45, 67, 89, 97]
Using the recursive algorithm:
67 was found at index 3 of the array.
93 was not found in the array.
Using the iterative algorithm:
22 was found at index 1 of the array.
70 was not found in the array.
</pre>
=={{header|XPL0}}==
{{trans|C}}
{{works with|EXPL-32}}
<syntaxhighlight lang="xpl0">
\Binary search
code CrLf=9, IntOut=11, Text=12;
def Size = 10;
integer A, X, I;
function integer DoBinarySearch(A, N, X);
integer A, N, X;
integer L, H, M;
begin
L:= 0; H:= N - 1;
while L <= H do
begin
M:= L + (H - L) / 2;
case of
A(M) < X: L:= M + 1;
A(M) > X: H:= M - 1
other return M;
end;
return -1;
end;
function integer DoBinarySearchRec(A, X, L, H);
integer A, X, L, H;
integer M;
begin
if H < L then
return -1;
M:= L + (H - L) / 2;
case of
A(M) > X: return DoBinarySearchRec(A, X, L, M - 1);
A(M) < X: return DoBinarySearchRec(A, X, M + 1, H)
other return M
end;
procedure PrintResult(X, IndX);
integer X, IndX;
begin
IntOut(0, X);
if IndX >= 0 then
begin
Text(0, " is at index ");
IntOut(0, IndX);
Text(0, ".")
end
else
Text(0, " is not found.");
CrLf(0)
end;
begin
\Sorted data
A:= [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782];
X:= 2;
I:= DoBinarySearch(A, Size, X);
PrintResult(X, I);
X:= 5;
I:= DoBinarySearchRec(A, X, 0, Size - 1);
PrintResult(X, I);
end
</syntaxhighlight>
{{out}}
<pre>
2 is at index 4.
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/archasm">* Binary search
BINSRCH LA R5,TABLE Begin of table
SR R2,R2 low = 0
LA R3,ENTRIES-1 high = N-1
LOOP CR R2,R3 while (low <= high)
JH NOTFOUND {
ARK R4,R2,R3 mid = low + high
SRL R4,1 mid = mid / 2
LA R1,1(R4) mid + 1
AHIK R0,R4,-1 mid - 1
MSFI R4,ENTRYL mid * length
AR R4,R5 Table[mid]
CLC 0(L'KEY,R4),SEARCH Compare
JE FOUND Equal? => Found
LOCRH R3,R0 High? => HIGH = MID-1
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_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
} else
}</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.
<
fcn(list,value, low,high){
if (high < low) return(Void); // not found
Line 5,596 ⟶ 8,113:
return(mid); // found
}(list,value,0,list.len()-1);
}</
<
foreach i in ([0..12]){
n:=bsearch(list,i);
if (Void==n) println("Not found: ",i);
else println("found ",i," at index ",n);
}</
{{out}}
<pre>
Line 5,620 ⟶ 8,137:
Not found: 12
</pre>
| |||