Binary search: Difference between revisions

Content added Content deleted
(Dialects of BASIC moved to the BASIC section.)
Line 1,395: Line 1,395:
-1
-1
Return</syntaxhighlight>
Return</syntaxhighlight>

=={{header|BASIC}}==
=={{header|BASIC}}==
'''Recursive'''
'''Recursive'''
Line 1,535: Line 1,536:
5 is not found.
5 is not found.
</pre>
</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}}===
==={{header|BBC BASIC}}===
Line 1,594: Line 1,644:
210 IF INDX% >= 0 THEN PRINT "is at index"; STR$(INDX%);"." ELSE PRINT "is not found."
210 IF INDX% >= 0 THEN PRINT "is at index"; STR$(INDX%);"." ELSE PRINT "is not found."
220 RETURN
220 RETURN
460 REM Binary search algorithm
480 REM Binary search algorithm
470 REM N% - number of elements
490 REM N% - number of elements; X - searched element; Result: INDX% - index of X
480 REM X - searched element
490 REM Result: INDX% - index of X
500 L% = 0: H% = N% - 1: FOUND% = 0
500 L% = 0: H% = N% - 1: FOUND% = 0
510 WHILE (L% <= H%) AND NOT FOUND%
510 WHILE (L% <= H%) AND NOT FOUND%
Line 1,640: Line 1,688:
350 IF BO<=UP THEN LET SEARCH=K
350 IF BO<=UP THEN LET SEARCH=K
360 END DEF</syntaxhighlight>
360 END DEF</syntaxhighlight>

==={{header|Liberty BASIC}}===
<syntaxhighlight lang="lb">
dim theArray(100)
for i = 1 to 100
theArray(i) = i
next i

print binarySearch(80,30,90)

wait

FUNCTION binarySearch(val, lo, hi)
IF hi < lo THEN
binarySearch = 0
ELSE
middle = int((hi + lo) / 2):print middle
if val < theArray(middle) then binarySearch = binarySearch(val, lo, middle-1)
if val > theArray(middle) then binarySearch = binarySearch(val, middle+1, hi)
if val = theArray(middle) then binarySearch = middle
END IF
END FUNCTION
</syntaxhighlight>


==={{header|Minimal BASIC}}===
==={{header|Minimal BASIC}}===
Line 1,695: Line 1,766:
</syntaxhighlight>
</syntaxhighlight>


=={{header|BASIC256}}==
==={{header|PureBasic}}===
Both recursive and iterative procedures are included and called in the code below.
====Recursive Solution====
<syntaxhighlight lang="basic256">function binarySearchR(array, valor, lb, ub)
<syntaxhighlight lang="purebasic">#Recursive = 0 ;recursive binary search method
#Iterative = 1 ;iterative binary search method
if ub < lb then
#NotFound = -1 ;search result if item not found
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>


;Recursive
====Iterative Solution====
Procedure R_BinarySearch(Array a(1), value, low, high)
<syntaxhighlight lang="basic256">function binarySearchI(array, valor)
Protected mid
lb = array[?,]
ub = array[?]
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
while lb <= ub
Procedure I_BinarySearch(Array a(1), value, low, high)
mitad = floor((lb + ub) / 2)
Protected mid
begin case
While low <= high
case array[mitad] > valor
ub = mitad - 1
mid = (low + high) / 2
case array[mitad] < valor
If a(mid) > value
lb = mitad + 1
high = mid - 1
else
ElseIf a(mid) < value
return mitad
low = mid + 1
end case
Else
ProcedureReturn mid
end while
return false
EndIf
Wend
end function</syntaxhighlight>
'''Test:'''
<syntaxhighlight lang="basic256">items = 10e5
dim array(items)
for n = 0 to items-1 : array[n] = n : next n


ProcedureReturn #NotFound
t0 = msec
EndProcedure
print binarySearchI(array, 3)

print msec - t0; " millisec"
Procedure search (Array a(1), value, method)
t1 = msec
Protected idx
print binarySearchR(array, 3, array[?,], array[?])
print msec - t1; " millisec"
Select method
end</syntaxhighlight>
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|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}}
{{out}}
'''Note: Array index starts at 0.'''
<pre>3
<pre>
839 millisec
C:\>cscript /nologo binary_search.vbs 4
3
4 not found
50 millisec</pre>

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}}==
=={{header|Batch File}}==
<syntaxhighlight lang="windowsnt">
<syntaxhighlight lang="windowsnt">
Line 4,027: Line 4,436:
{BS {B} 12345} -> 12345 is at array[6172]
{BS {B} 12345} -> 12345 is at array[6172]
</syntaxhighlight>
</syntaxhighlight>
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
dim theArray(100)
for i = 1 to 100
theArray(i) = i
next i


print binarySearch(80,30,90)

wait

FUNCTION binarySearch(val, lo, hi)
IF hi < lo THEN
binarySearch = 0
ELSE
middle = int((hi + lo) / 2):print middle
if val < theArray(middle) then binarySearch = binarySearch(val, lo, middle-1)
if val > theArray(middle) then binarySearch = binarySearch(val, middle+1, hi)
if val = theArray(middle) then binarySearch = middle
END IF
END FUNCTION
</syntaxhighlight>
=={{header|Logo}}==
=={{header|Logo}}==
<syntaxhighlight lang="logo">to bsearch :value :a :lower :upper
<syntaxhighlight lang="logo">to bsearch :value :a :lower :upper
Line 5,356: Line 5,744:
?- bin_search(5,[1,2,4,8],Result).
?- bin_search(5,[1,2,4,8],Result).
Result = -1.</pre>
Result = -1.</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|Python}}==
=={{header|Python}}==
===Python: Iterative===
===Python: Iterative===
Line 6,016: Line 6,304:
needles.select{|needle| haystack.bsearch{|hay| needle <=> hay} } # => [0, 45, 24324]
needles.select{|needle| haystack.bsearch{|hay| needle <=> hay} } # => [0, 45, 24324]
</syntaxhighlight>Which is 60% faster than "needles & haystack".
</syntaxhighlight>Which is 60% faster than "needles & haystack".
=={{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|Rust}}==
=={{header|Rust}}==
'''Iterative'''
'''Iterative'''
Line 6,826: Line 7,095:
}
}
}</syntaxhighlight>
}</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|UNIX Shell}}==
=={{header|UNIX Shell}}==


Line 6,936: Line 7,156:


echo "1 2 3 4 6 7 8 9" | binsearch 6</syntaxhighlight>
echo "1 2 3 4 6 7 8 9" | binsearch 6</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|Vedit macro language}}==
=={{header|Vedit macro language}}==
'''Iterative'''
'''Iterative'''
Line 7,082: Line 7,192:
}
}
return(0) // not found</syntaxhighlight>
return(0) // not found</syntaxhighlight>
=={{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|Vlang}}==
=={{header|Vlang}}==
<syntaxhighlight lang="vlang">fn binary_search_rec(a []f64, value f64, low int, high int) int { // recursive
<syntaxhighlight lang="vlang">fn binary_search_rec(a []f64, value f64, low int, high int) int { // recursive
Line 7,321: Line 7,394:
5 is not found.
5 is not found.
</pre>
</pre>
=={{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|z/Arch Assembler}}==
=={{header|z/Arch Assembler}}==
This optimized version for z/Arch, uses six general regs and avoid branch misspredictions for high/low cases.
This optimized version for z/Arch, uses six general regs and avoid branch misspredictions for high/low cases.
Line 7,408: Line 7,448:
Not found: 12
Not found: 12
</pre>
</pre>
=={{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>
Retrieved from "https://rosettacode.org/wiki/Binary_search"