Binary search: Difference between revisions
m
syntax highlighting fixup automation
(Binary search in BASIC256) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 148:
=={{header|11l}}==
<
V low = 0
V high = l.len - 1
Line 159:
E
R mid
R -1</
=={{header|360 Assembly}}==
<
BINSEAR CSECT
USING BINSEAR,R13 base register
Line 232:
XDEC DS CL12 temp
YREGS
END BINSEAR</
{{out}}
<pre>
Line 247:
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.
<
jmp test
Line 349:
rst 0
</syntaxhighlight>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program binSearch64.s */
Line 589:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
Value find at index : 0
Line 604:
=={{header|ACL2}}==
<
(cons name
(compress1 name
Line 664:
(populate-array-ordered
(defarray 'haystack *dim* 0)
*dim*)))</
=={{header|Action!}}==
<
INT low,high,mid
Line 712:
Test(a,8,10)
Test(a,8,7)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Binary_search.png Screenshot from Atari 8-bit computer]
Line 727:
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 780:
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 837:
Test ((2, 4, 6, 8, 9), 9);
Test ((2, 4, 6, 8, 9), 5);
end Test_Binary_Search;</
Sample output:
<pre>
Line 849:
=={{header|ALGOL 68}}==
<
MODE ELEMENT = STRING;
Line 897:
test search(recursive binary search, test cases)
)
END</
{{out}}
Shows iterative search output - recursive search output is the same.
Line 909:
=={{header|ALGOL W}}==
Ieterative and recursive binary search procedures, from the pseudo code. Finds the left most occurance/insertion point.
<
% recursive binary search, left most insertion point %
integer procedure binarySearchLR ( integer array A ( * )
Line 957:
end for_s
end
end.</
{{out}}
<pre>
Line 973:
{{works with|Dyalog APL}}
<
⎕IO(⍺{ ⍝ first lower bound is start of array
⍵<⍺:⍬ ⍝ if high < low, we didn't find it
Line 982:
}⍵)⎕IO+(≢⍺)-1 ⍝ first higher bound is top of array
}
</syntaxhighlight>
=={{header|AppleScript}}==
<
repeat until (l = r)
set m to (l + r) div 2
Line 1,010:
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)</
{{output}}
Line 1,020:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<
/* ARM assembly Raspberry PI */
Line 1,297:
iMagicNumber: .int 0xCCCCCCCD
</syntaxhighlight>
=={{header|Arturo}}==
<
if high < low -> return ø
mid: shr low+high 1
Line 1,320:
if? not? null? i -> print ["found" v "at index:" i]
else -> print [v "not found"]
]</
{{out}}
Line 1,331:
=={{header|AutoHotkey}}==
<
StringSplit, A, array, `, ; creates associative array
MsgBox % x := BinarySearch(A, 4, 1, A0) ; Recursive
Line 1,363:
}
Return not_found
}</
=={{header|AWK}}==
Line 1,370:
{{works with|Nawk}}
'''Recursive'''
<
if (right < left) return 0
middle = int((right + left) / 2)
Line 1,377:
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 1,387:
}
return 0
}</
=={{header|Axe}}==
Line 1,394:
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 1,409:
End
-1
Return</
=={{header|BASIC}}==
Line 1,415:
{{works with|FreeBASIC}}
{{works with|RapidQ}}
<
DIM middle AS Integer
Line 1,431:
END SELECT
END IF
END FUNCTION</
'''Iterative'''
{{works with|FreeBASIC}}
{{works with|RapidQ}}
<
DIM middle AS Integer
Line 1,451:
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 1,477:
search test(), 4
search test(), 8
search test(), 20</
Output:
Value 4 not found
Line 1,484:
==={{header|ASIC}}===
<
REM Binary search
DIM A(10)
Line 1,545:
ENDIF
RETURN
</syntaxhighlight>
{{out}}
<pre>
Line 1,553:
==={{header|BBC BASIC}}===
<
array%() = 7, 14, 21, 28, 35, 42, 49, 56, 63, 70
Line 1,575:
H% /= 2
UNTIL H%=0
IF S%=A%(B%) THEN = B% ELSE = -1</
==={{header|FreeBASIC}}===
<
'returns the index of the target number, or -1 if it is not in the array
dim as uinteger lo = lbound(array), hi = ubound(array), md = (lo + hi)\2
Line 1,589:
wend
return -1
end function</
==={{header|IS-BASIC}}===
<
110 RANDOMIZE
120 NUMERIC ARR(1 TO 20)
Line 1,618:
340 LOOP WHILE BO<=UP AND T(K)<>N
350 IF BO<=UP THEN LET SEARCH=K
360 END DEF</
==={{header|Minimal BASIC}}===
Line 1,624:
{{works with|Commodore BASIC|3.5}}
{{works with|Nascom ROM BASIC|4.7}}
<
10 REM Binary search
20 LET N = 10
Line 1,671:
670 LET I1 = -1
680 RETURN
</syntaxhighlight>
=={{header|BASIC256}}==
====Recursive Solution====
<
if ub < lb then
return false
Line 1,684:
if valor = array[mitad] then return mitad
end if
end function</
====Iterative Solution====
<
lb = array[?,]
ub = array[?]
Line 1,703:
end while
return false
end function</
'''Test:'''
<
dim array(items)
for n = 0 to items-1 : array[n] = n : next n
Line 1,715:
print binarySearchR(array, 3, array[?,], array[?])
print msec - t1; " millisec"
end</
{{out}}
<pre>3
Line 1,723:
=={{header|Batch File}}==
<
@echo off & setlocal enabledelayedexpansion
Line 1,772:
echo . binchop required !b! iterations
endlocal & exit /b 0
</syntaxhighlight>
=={{header|BQN}}==
Line 1,778:
BQN has two builtin functions for binary search: <code>⍋</code>(Bins Up) and <code>⍒</code>(Bins Down). This is a recursive method.
<
BS ⟨a, value⟩:
BS ⟨a, value, 0, ¯1+≠a⟩;
Line 1,791:
}
•Show BSearch ⟨8‿30‿35‿45‿49‿77‿79‿82‿87‿97, 97⟩</
<syntaxhighlight lang=text>9</
=={{header|Brat}}==
<
true? high < low
{ null }
Line 1,825:
null? index
{ p "Not found" }
{ p "Found at index: #{index}" }</
=={{header|C}}==
<
int bsearch (int *a, int n, int x) {
Line 1,881:
return 0;
}
</syntaxhighlight>
{{output}}
<pre>
Line 1,890:
=={{header|C sharp|C#}}==
'''Recursive'''
<
using System;
Line 1,960:
}
}
}</
'''Iterative'''
<
using System;
Line 2,034:
}
}
}</
'''Example'''
<
using System;
Line 2,078:
#endif
}
}</
'''Output'''
Line 2,117:
=={{header|C++}}==
'''Recursive'''
<
template <class T> int binsearch(const T array[], int low, int high, T value) {
if (high < low) {
Line 2,143:
return 0;
}</
'''Iterative'''
<
int binSearch(const T arr[], int len, T what) {
int low = 0;
Line 2,159:
}
return -1; // indicate not found
}</
'''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
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.
<
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.
<
The <code>equal_range()</code> function returns a pair of the results of <code>lower_bound()</code> and <code>upper_bound()</code>.
<
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.
<
=={{header|Chapel}}==
'''iterative''' -- almost a direct translation of the pseudocode
<
var low = A.domain.dim(1).low;
var high = A.domain.dim(1).high;
Line 2,195:
}
writeln(binsearch([3, 4, 6, 9, 11], 9));</
{{out}}
Line 2,202:
=={{header|Clojure}}==
'''Recursive'''
<
([coll t]
(bsearch coll 0 (dec (count coll)) t))
Line 2,217:
; we've found our target
; so return its index
(= mth t) m)))))</
=={{header|CLU}}==
<
% If the item is found, returns `true' and the index;
% if the item is not found, returns `false' and the leftmost insertion point
Line 2,266:
end
end
end start_up</
{{out}}
<pre>1 not found, would be inserted at location 1
Line 2,291:
=={{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 2,308:
END-SEARCH
.
END PROGRAM binary-search.</
=={{header|CoffeeScript}}==
'''Recursive'''
<
do recurse = (low = 0, high = xs.length - 1) ->
mid = Math.floor (low + high) / 2
Line 2,319:
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 2,329:
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 2,338:
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 2,350:
=={{header|Common Lisp}}==
'''Iterative'''
<
(let ((low 0)
(high (1- (length array))))
Line 2,363:
(setf low (1+ middle)))
(t (return middle)))))))</
'''Recursive'''
<
(if (< high low)
nil
Line 2,376:
(binary-search value array (1+ middle) high))
(t middle)))))</
=={{header|Crystal}}==
'''Recursive'''
<
def binary_search(val, low = 0, high = (size - 1))
return nil if high < low
Line 2,404:
puts "#{val} not found in array"
end
end</
'''Iterative'''
<
def binary_search_iterative(val)
low, high = 0, size - 1
Line 2,434:
puts "#{val} not found in array"
end
end</
{{out}}
<pre>
Line 2,445:
=={{header|D}}==
<
/// Recursive.
Line 2,485:
// Standard Binary Search:
!items.equalRange(x).empty);
}</
{{out}}
<pre> 1 false false false
Line 2,497:
=={{header|E}}==
<
def binarySearch(collection, value) {
var low := 0
Line 2,510:
}
return null
}</
=={{header|EasyLang}}==
<syntaxhighlight lang=text>func bin_search val . a[] res .
low = 0
high = len a[] - 1
Line 2,530:
a[] = [ 2 4 6 8 9 ]
call bin_search 8 a[] r
print r</
=={{header|Eiffel}}==
Line 2,536:
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 2,655:
end
end</
=={{header|Elixir}}==
<
def search(list, value), do: search(List.to_tuple(list), value, 0, length(list)-1)
Line 2,679:
index -> IO.puts "found #{val} at index #{index}"
end
end)</
{{out}}
Line 2,691:
=={{header|Emacs Lisp}}==
<
(defun binary-search (value array)
(let ((low 0)
Line 2,701:
((< (aref array middle) value)
(setf low (1+ middle)))
(t (cl-return middle)))))))</
=={{header|Erlang}}==
<
%% Author: Abhay Jain
Line 2,730:
Mid
end
end.</
=={{header|Euphoria}}==
===Recursive===
<
integer mid, cmp
if high < low then
Line 2,749:
end if
end if
end function</
===Iterative===
<
integer low, high, mid, cmp
low = 1
Line 2,767:
end while
return 0 -- not found
end function</
=={{header|F Sharp|F#}}==
Generic recursive version, using #light syntax:
<
if (high < low) then
null
Line 2,782:
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.
<
: binary-search ( seq elt -- index/f )
[ [ <=> ] curry search ] keep = [ drop f ] unless ;</
=={{header|FBSL}}==
FBSL has built-in QuickSort() and BSearch() functions:
<
DIM va[], sign = {1, -1}, toggle
Line 2,814:
" in ", GetTickCount() - gtc, " milliseconds"
PAUSE</
Output:<pre>Loading ... done in 906 milliseconds
Sorting ... done in 547 milliseconds
Line 2,823:
'''Iterative:'''
<
DIM va[]
Line 2,851:
WEND
RETURN -1
END FUNCTION</
Output:<pre>Loading ... done in 391 milliseconds
3141592.65358979 found at index 1000000 in 62 milliseconds
Line 2,858:
'''Recursive:'''
<
DIM va[]
Line 2,882:
END IF
RETURN midp
END FUNCTION</
Output:<pre>Loading ... done in 390 milliseconds
3141592.65358979 found at index 1000000 in 938 milliseconds
Line 2,890:
=={{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 2,920:
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 2,942:
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 2,968:
end if
end do
end function binarySearch_I</
===Iterative, exclusive bounds, three-way test.===
Line 2,979:
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 2,998:
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 3,010:
====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 3,029:
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 3,050:
Straightforward translation of imperative iterative algorithm.
<
fun main(as: [n]int, value: int): int =
let low = 0
Line 3,064:
else (mid, mid-1) -- Force termination.
in low
</syntaxhighlight>
=={{header|GAP}}==
<
local low, high, mid;
low := 1;
Line 3,089:
# fail
Find(u, 35);
# 5</
=={{header|Go}}==
'''Recursive''':
<
if high < low {
return -1
Line 3,104:
}
return mid
}</
'''Iterative''':
<
low := 0
high := len(a) - 1
Line 3,120:
}
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.
Line 3,134:
Both solutions use ''sublists'' and a tracking offset in preference to "high" and "low".
====Recursive Solution====
<
def binSearchR
//define binSearchR closure.
Line 3,148:
: [index: offset + m]
}
</syntaxhighlight>
====Iterative Solution====
<
def a = aList
def offset = 0
Line 3,167:
}
return ["insertion point": offset]
}</
Test:
<
def random = new Random()
while (a.size() < 20) { a << random.nextInt(30) }
Line 3,185:
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 3,203:
The algorithm itself, parametrized by an "interrogation" predicate ''p'' in the spirit of the explanation above:
<
-- BINARY SEARCH --------------------------------------------------------------
Line 3,254:
case found of
Nothing -> "' Not found"
Just x -> "' found at index " ++ show x</
{{Out}}
<pre>'mu' found at index 9</pre>
Line 3,261:
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 3,306:
("' " ++)
(("' found at index " ++) . show)
(findIndexBinary (compare needle) haystack)</
{{Out}}
<pre>'lambda' found at index 8</pre>
Line 3,316:
It returns the result of applying '''f''' until '''p''' holds.
<
-- BINARY SEARCH USING THE ITERATIVE ALGORITHM
Line 3,365:
("' " ++)
(("' found at index " ++) . show)
(findIndexBinary_ (compare needle) haystack)</
{{Out}}
<pre>'kappa' found at index 7</pre>
=={{header|HicEst}}==
<
array = NINT( RAN(n) )
Line 3,401:
ENDIF
ENDDO
END</
<
5 has position 0 in 0 0 1 2 3 3 4 6 7 8</
=={{header|Hoon}}==
<
=/ lo=@ud 0
=/ hi=@ud (dec (lent arr))
Line 3,415:
?: (lth x val) $(hi (dec mid))
?: (gth x val) $(lo +(mid))
mid</
=={{header|Icon}} and {{header|Unicon}}==
Only a recursive solution is shown here.
<
if *A = 0 then fail
mid := *A/2 + 1
Line 3,429:
}
return mid
end</
A program to test this is:
<
target := integer(!args) | 3
every put(A := [], 1 to 18 by 2)
Line 3,443:
every writes(!A," ")
write()
end</
with some sample runs:
<pre>
Line 3,478:
=={{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 3,499:
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 3,511:
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 3,543:
}
}
}</
'''Recursive'''
<
public static int binarySearch(int[] haystack, int needle, int lo, int hi) {
Line 3,574:
}
}
}</
'''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 3,586:
// 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 3,608:
}
return mid;
}</
Iterative binary search implementation
<
var mid, lo = 0,
hi = a.length - 1;
Line 3,626:
}
return null;
}</
===ES6===
Line 3,632:
Recursive and iterative, by composition of pure functions, with tests and output:
<
'use strict';
Line 3,788:
// MAIN ---
return main();
})();</
{{Out}}
<pre>[
Line 3,833:
If the input array is sorted, then binarySearch(value) as defined here 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.
Recursive solution:<
# To avoid copying the array, simply pass in the current low and high offsets
def binarySearch(low; high):
Line 3,843:
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 3,901:
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 3,916:
{{works with|Julia|0.6}}
'''Iterative''':
<
low = 1
high = length(lst)
Line 3,930:
end
return 0
end</
'''Recursive''':
<
if isempty(lst) return 0 end
if low ≥ high
Line 3,950:
return mid
end
end</
=={{header|K}}==
Recursive:
<syntaxhighlight lang=K>
bs:{[a;t]
if[0=#a; :_n];
Line 3,969:
{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 4,009:
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 4,018:
=={{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 4,047:
{BS {B} 100} -> 100 is not found
{BS {B} 12345} -> 12345 is at array[6172]
</syntaxhighlight>
=={{header|Liberty BASIC}}==
<syntaxhighlight lang=lb>
dim theArray(100)
for i = 1 to 100
Line 4,070:
END IF
END FUNCTION
</syntaxhighlight>
=={{header|Logo}}==
<
if :upper < :lower [output []]
localmake "mid int (:lower + :upper) / 2
Line 4,079:
if item :mid :a < :value [output bsearch :value :a :mid+1 :upper]
output :mid
end</
=={{header|Lolcode}}==
'''Iterative'''
<
HAI 1.2
CAN HAS STDIO?
Line 4,171:
KTHXBYE
end</
Output
<pre>
Line 4,186:
=={{header|Lua}}==
'''Iterative'''
<
local low = 1
local high = #list
Line 4,197:
end
return false
end</
'''Recursive'''
<
local function search(low, high)
if low > high then return false end
Line 4,208:
end
return search(1,#list)
end</
=={{header|M2000 Interpreter}}==
<
\\ binary search
const N=10
Line 4,257:
Print A()
</syntaxhighlight>
=={{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 4,269:
dnl
binarysearch(`a',5,1,asize)
binarysearch(`a',8,1,asize)</
Output:
<pre>
Line 4,280:
'''Recursive'''
<
description "recursive binary search";
if high < low then
Line 4,294:
end if
end if
end proc:</
'''Iterative'''
<
description "iterative binary search";
local low, high;
Line 4,313:
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 4,331:
> PP[ 3 ];
13</
=={{header|Mathematica}} / {{header|Wolfram Language}}==
'''Recursive'''
<
Module[{mid = lo + Round@((hi - lo)/2)},
If[hi < lo, Return[-1]];
Line 4,343:
True, mid]
];
]</
'''Iterative'''
<
While[lo <= hi,
mid = lo + Round@((hi - lo)/2);
Line 4,354:
];
Return[-1];
]</
=={{header|MATLAB}}==
'''Recursive'''
<
if( high < low )
Line 4,377:
end
end</
Sample Usage:
<
ans =
7</
'''Iterative'''
<
low = 1;
Line 4,404:
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 4,432:
0
find(a, 421);
82</
=={{header|MAXScript}}==
'''Iterative'''
<
(
lower = 1
Line 4,460:
arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10)
result = binarySearchIterative arr 6</
'''Recursive'''
<
(
if lower == upper then
Line 4,491:
arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10)
result = binarySearchRecursive arr 6 1 arr.count</
=={{header|MiniScript}}==
'''Recursive:'''
<
if high < low then return null
mid = floor((low + high) / 2)
Line 4,501:
if A[mid] < value then return binarySearch(A, value, mid+1, high)
return mid
end function</
'''Iterative:'''
<
low = 0
high = A.len - 1
Line 4,518:
end if
end while
end function</
=={{header|N/t/roff}}==
{{works with|GNU TROFF|1.22.2}}
<syntaxhighlight lang=text>.de end
..
.de array
Line 4,561:
.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 4,577:
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 4,590:
'tom bsearch . ( => 0 )
'kenny bsearch . ( => 2 )
'tony bsearch . ( => -1)</
=={{header|Objeck}}==
'''Iterative'''
<
bundle Default {
Line 4,625:
}
}
}</
=={{header|Objective-C}}==
'''Iterative'''
<
@interface NSArray (BinarySearch)
Line 4,669:
}
return 0;
}</
'''Recursive'''
<
@interface NSArray (BinarySearchRecursive)
Line 4,708:
}
return 0;
}</
'''Library'''
{{works with|Mac OS X|10.6+}}
<
int main()
Line 4,725:
}
return 0;
}</
Using Core Foundation (part of Cocoa, all versions):
<
CFComparisonResult myComparator(const void *x, const void *y, void *context) {
Line 4,745:
}
return 0;
}</
=={{header|OCaml}}==
'''Recursive'''
<
if high = low then
if a.(low) = value then
Line 4,761:
binary_search a value (mid + 1) high
else
mid</
Output:
<pre>
Line 4,775:
=={{header|Octave}}==
'''Recursive'''
<
if ( high < low )
i = 0;
Line 4,788:
endif
endif
endfunction</
'''Iterative'''
<
low = 1;
high = numel(array);
Line 4,805:
endif
endwhile
endfunction</
'''Example of using'''
<
disp(r);
binsearch_r(r, 5, 1, numel(r))
binsearch(r, 5)</
=={{header|Ol}}==
<
(define (binary-search value vector)
(let helper ((low 0)
Line 4,829:
(binary-search 12 [1 2 3 4 5 6 7 8 9 10 11 12 13]))
; ==> 12
</syntaxhighlight>
=={{header|ooRexx}}==
<
data = .array~of(1, 3, 5, 7, 9, 11)
-- search keys with a number of edge cases
Line 4,885:
end
return 0
</syntaxhighlight>
Output:
<pre>
Line 4,907:
=={{header|Oz}}==
'''Recursive'''
<
fun {BinarySearch Arr Val}
fun {Search Low High}
Line 4,927:
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 4,947:
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 4,957:
{{trans|N/t/roff}}
<
local(
minm = 1,
Line 4,980:
print("Item exists on index ", idx), \
print("Item does not exist anywhere.") \
)</
=={{header|Pascal}}==
'''Iterative'''
<
var
l, m, h: integer;
Line 5,008:
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 5,032:
}
return -1;
}</
'''Recursive'''
<
my ($array_ref, $value, $left, $right) = @_;
return -1 if ($right < $left);
Line 5,047:
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)
<!--<
<span style="color: #008080;">global</span> <span style="color: #008080;">function</span> <span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">needle</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">haystack</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
Line 5,072:
<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>
<!--</
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
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- -1</span>
Line 5,085:
<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>
<!--</
=={{header|PHP}}==
'''Iterative'''
<
{
do
Line 5,107:
return $guess;
}</
'''Recursive'''
<
{
$guess = (int)($start + ( ( $end - $start ) / 2 ));
Line 5,123:
return $guess;
}</
=={{header|Picat}}==
===Iterative===
<
A = [2, 4, 6, 8, 9],
TestValues = [2,1,8,10,9,5],
Line 5,172:
end,
V = V1.
</syntaxhighlight>
{{out}}
Line 5,185:
===Recursive version===
<
Ret = binary_search_rec(A,Value, 1, A.length).
Line 5,197:
Mid1 := binary_search_rec(A, Value, Mid1+1, High)
end,
Mid = Mid1.</
=={{header|PicoLisp}}==
'''Recursive'''
<
(unless (=0 Len)
(let (N (inc (/ Len 2)) L (nth Lst N))
Line 5,208:
((> 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 5,217:
-> NIL</pre>
'''Iterative'''
<
(use (N L)
(loop
Line 5,227:
(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 5,237:
=={{header|PL/I}}==
<
search: procedure (A, M) returns (fixed binary);
declare (A(*), M) fixed binary;
Line 5,252:
end;
return (lbound(A,1)-1);
end search;</
=={{header|Pop11}}==
'''Iterative'''
<
lvars low = 1, high = length(A), mid;
while low <= high do
Line 5,276:
BinarySearch(A, 4) =>
BinarySearch(A, 5) =>
BinarySearch(A, 8) =></
'''Recursive'''
<
define do_it(low, high);
if high < low then
Line 5,293:
enddefine;
do_it(1, length(A));
enddefine;</
=={{header|PowerShell}}==
<
function BinarySearch-Iterative ([int[]]$Array, [int]$Value)
{
Line 5,363:
}
}
</syntaxhighlight>
<
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 5,380:
=={{header|Prolog}}==
Tested with Gnu-Prolog.
<
length(List,N), bin_search_inner(Elt,List,1,N,Result).
Line 5,402:
MidElt > Elt,
NewEnd is Mid-1,
bin_search_inner(Elt,List,Begin,NewEnd,Result).</
{{out|Output examples}}
Line 5,413:
=={{header|PureBasic}}==
Both recursive and iterative procedures are included and called in the code below.
<
#Iterative = 1 ;iterative binary search method
#NotFound = -1 ;search result if item not found
Line 5,499:
Input()
CloseConsole()
EndIf</
Sample output:
<pre>
Line 5,515:
=={{header|Python}}==
===Python: Iterative===
<
low = 0
high = len(l)-1
Line 5,523:
elif l[mid] < value: low = mid+1
else: return mid
return -1</
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:
<
def findIndexBinary(p):
def isFound(bounds):
Line 5,618:
if __name__ == '__main__':
main()
</syntaxhighlight>
{{Out}}
<pre>Word found at index 6
Line 5,624:
===Python: Recursive===
<
if not l: return -1
if(high == -1): high = len(l)-1
Line 5,633:
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).
Line 5,639:
This time using the recursive definition:
<
def findIndexBinary_(p):
def go(xs):
Line 5,706:
'Word of given length found at index ' + str(mb2)
)
)</
{{Out}}
<pre>Word found at index 9
Line 5,713:
===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 5,720:
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 5,745:
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.
<
[ stack ] is nest.bs ( --> n )
[ stack ] is test.bs ( --> n )
Line 5,781:
[ say " could go into position " ]
echo
say "." cr ] is task ( [ n --> n )</
{{out}}
Line 5,797:
=={{header|R}}==
'''Recursive'''
<
if ( high < low ) {
return(NULL)
Line 5,809:
mid
}
}</
'''Iterative'''
<
low = 1
high = length(A)
Line 5,825:
}
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 5,847:
[else m])]))
(loop 0 (vector-length v)))
</syntaxhighlight>
Examples:
<pre>
Line 5,857:
(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
binary_search { $x cmp @a[$^i] }, 0, @a.end
}</
'''Iterative'''
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang=raku
until $lo > $hi {
my Int $mid = ($lo + $hi) div 2;
Line 5,872:
}
fail;
}</
'''Recursive'''
{{trans|Haskell}}
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang=raku
$lo <= $hi or fail;
my Int $mid = ($lo + $hi) div 2;
Line 5,884:
default { $mid }
}
}</
=={{header|REXX}}==
Line 5,890:
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)
<
@= 3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181,
193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401 409 421 433,
Line 5,919:
if ?=y then return mid
if y>? then return binarySearch(low, mid-1)
return binarySearch(mid+1, high)</
{{out|output|text= when using the input of: <tt> 499.1 </tt>}}
<pre>
Line 5,933:
===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,
Line 5,957:
end /*while*/
say ? " wasn't found in the list." /*stick a fork in it, we're all done. */</
{{out|output|text= when using the input of: <tt> -314 </tt>}}
<pre>
Line 5,972:
=={{header|Ring}}==
<
decimals(0)
array = [7, 14, 21, 28, 35, 42, 49, 56, 63, 70]
Line 6,003:
return -1
ok
</syntaxhighlight>
Output:
<pre>
Line 6,011:
=={{header|Ruby}}==
'''Recursive'''
<
def binary_search(val, low=0, high=(length - 1))
return nil if high < low
Line 6,034:
puts "#{val} not found in array"
end
end</
'''Iterative'''
<
def binary_search_iterative(val)
low, high = 0, length - 1
Line 6,063:
puts "#{val} not found in array"
end
end</
{{out}}
<pre>
Line 6,074:
'''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|Run BASIC}}==
'''Recursive'''
<
global theArray
for i = 1 to 100
Line 6,099:
if val = theArray(middle) then binarySearch = middle
END IF
END FUNCTION</
=={{header|Rust}}==
'''Iterative'''
<
let mut lower = 0 as usize;
let mut upper = v.len() - 1;
Line 6,119:
None
}</
=={{header|Scala}}==
'''Recursive'''
<
def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {
case _ if high < low => None
Line 6,131:
}
recurse(0, a.size - 1)
}</
'''Iterative'''
<
var low: Int = 0
var high: Int = xs.size - 1
Line 6,144:
}
None //not found
}</
'''Test'''
<
val odds = 1 to n by 2
val result = (0 to n).flatMap(binarySearch(odds, _))
Line 6,155:
}
def main() = testBinarySearch(12)</
Output:
<pre>Range(1, 3, 5, 7, 9, 11) are odd natural numbers
Line 6,167:
=={{header|Scheme}}==
'''Recursive'''
<
(let helper ((low 0)
(high (- (vector-length vector) 1)))
Line 6,177:
((< (vector-ref vector middle) value)
(helper (+ middle 1) high))
(else middle))))))</
Example:
<pre>
Line 6,190:
=={{header|Seed7}}==
'''Iterative'''
<
result
var integer: result is 0;
Line 6,209:
end if;
end while;
end func;</
'''Recursive'''
<
result
var integer: result is 0;
Line 6,226:
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 6,240:
binarySearch(A, value, mid + 1, high) when A[mid] < value
else
mid;</
=={{header|Sidef}}==
Iterative:
<
var l = 0
Line 6,257:
return -1
}</
Recursive:
<
high < low && return -1
var middle = ((high+low) // 2)
Line 6,274:
}
}
}</
Usage:
<
=={{header|Simula}}==
<
Line 6,367:
END;
END</
{{out}}
<pre>
Line 6,408:
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 6,504:
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 6,595:
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 6,628:
</pre>
The test program:
<
with SPARK_IO;
Line 6,712:
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 6,727:
=={{header|Standard ML}}==
'''Recursive'''
<
let
fun aux slice =
Line 6,743:
in
aux (ArraySlice.full arr)
end</
Usage:
<pre>
Line 6,785:
=={{header|Swift}}==
'''Recursive'''
<
var recurse: ((Int, Int) -> Int?)!
recurse = {(low, high) in switch (low + high) / 2 {
Line 6,794:
}}
return recurse(0, xs.count - 1)
}</
'''Iterative'''
<
var (low, high) = (0, xs.count - 1)
while low <= high {
Line 6,806:
}
return nil
}</
'''Test'''
<
let odds = Array(stride(from: 1, through: n, by: 2))
let result = flatMap(0...n) {binarySearch(odds, $0)}
Line 6,822:
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 6,834:
=={{header|Symsyn}}==
<
a : 1 : 2 : 27 : 44 : 46 : 57 : 77 : 154 : 212
Line 6,865:
"'result = ' R" []
</syntaxhighlight>
=={{header|Tcl}}==
ref: [http://wiki.tcl.tk/22796 Tcl wiki]
<
set len [llength $lst]
if {$len == 0} {
Line 6,893:
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 6,902:
puts "element $x found at index $idx"
}
}</
=={{header|TI-83 BASIC}}==
<
:Disp "INPUT A LIST:"
:Input L1
Line 6,931:
:Disp A
:Disp "IS NOT IN"
:Disp L1</
=={{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
Line 6,954:
If a@ > @(d@) Then Return (FUNC(_binarySearch (a@, d@+1, c@)))
If a@ = @(d@) Then Return (d@) ' We found it, return index!
EndIf</
=={{header|UNIX Shell}}==
Line 6,960:
'''Reading values line by line'''
<
#!/bin/ksh
# This should work on any clone of Bourne Shell, ksh is the fastest.
Line 6,972:
array[${#array[*]}]=$line
done
</syntaxhighlight>
'''Iterative'''
<
left=0
right=$(($size - 1))
Line 6,992:
done
echo 'ERROR 404 : NOT FOUND'
</syntaxhighlight>
'''Recursive'''
<syntaxhighlight lang=text> No code yet </
=={{header|UnixPipes}}==
'''Parallel'''
<
a=$1; s=$2; l=$3; r=$4;
mid=$(expr ${#a[*]} / 2);
Line 7,016:
}
echo "1 2 3 4 6 7 8 9" | binsearch 6</
=={{header|VBA}}==
'''Recursive version''':
<
'search for "value" in ordered array a(low..high)
'return index point if found, -1 if not found
Line 7,036:
BinarySearch = midd
End If
End Function</
Here are some test functions:
<
Dim a(1 To 100)
'create an array with values = multiples of 10
Line 7,050:
a = Array("AA", "Maestro", "Mario", "Master", "Mattress", "Mister", "Mistress", "ZZ")
Debug.Print BinarySearch(a, w, LBound(a), UBound(a))
End Sub</
and sample output:
<pre>
Line 7,068:
'''Iterative version:'''
<
'search for "value" in array a
'return index point if found, -1 if not found
Line 7,086:
Loop
BinarySearch2 = -1 'not found
End Function</
=={{header|VBScript}}==
{{trans|BASIC}}
'''Recursive'''
<
If hi < lo Then
binary_search = 0
Line 7,117:
WScript.StdOut.Write n & " not found"
WScript.StdOut.WriteLine
End If</
{{out}}
'''Note: Array index starts at 0.'''
Line 7,136:
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 7,165:
}
}
return(0) // not found</
=={{header|Visual Basic .NET}}==
'''Iterative'''
<
Dim low As Integer = 0
Dim high As Integer = A.Length - 1
Line 7,186:
Return Nothing
End Function</
'''Recursive'''
<
Dim middle As Integer = 0
Line 7,204:
Return middle
End If
End Function</
=={{header|Vlang}}==
<
if high <= low {
return -1
Line 7,241:
println(binary_search_it(f_list,9))
println(binary_search_it(f_list,15))
}</
{{out}}
Line 7,253:
=={{header|Wortel}}==
{{trans|JavaScript}}
<
@var rec &[a v l h] [
@if < h l @return null
Line 7,276:
]
null
]</
=={{header|Wren}}==
<
static recursive(a, value, low, high) {
if (high < low) return -1
Line 7,326:
System.print(" %(value) was not found in the array.")
}
}</
{{out}}
Line 7,344:
{{trans|C}}
{{works with|EXPL-32}}
<
\Binary search
code CrLf=9, IntOut=11, Text=12;
Line 7,404:
PrintResult(X, I);
end
</syntaxhighlight>
{{out}}
<pre>
Line 7,413:
=={{header|Yabasic}}==
{{trans|Lua}}
<
return int(n + .5)
end sub
Line 7,444:
print binarySearch(list(), 3)
print peek("millisrunning")</
=={{header|z/Arch Assembler}}==
This optimized version for z/Arch, uses six general regs and avoid branch misspredictions for high/low cases.
<
BINSRCH LA R5,TABLE Begin of table
SR R2,R2 low = 0
Line 7,464:
LOCRH R3,R0 High? => HIGH = MID-1
LOCRL R2,R1 Low? => LOW = MID+1
J LOOP }</
=={{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 7,476:
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 7,504:
{{trans|FreeBASIC}}
Iterative method:
<
20 DIM t(10)
30 FOR i=1 TO 10
Line 7,523:
180 IF idx=0 THEN PRINT " not found": RETURN
190 PRINT " found at index ";idx: RETURN
</syntaxhighlight>
|