Binary search: Difference between revisions

Line 1:

~~{{task|Classic CS problems and programs}}~~[[Category:Recursion]]

[[Category:Recursion]]

A binary search divides a range of values into halves, and continues to narrow down the field of search until the unknown value is found. It is the classic example of a "divide and conquer" algorithm.

Line 146:

:* [http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken].

=={{header|11l}}==

<syntaxhighlight lang=11l>F binary_search(l, value)

<syntaxhighlight lang="11l">F binary_search(l, value)

V low = 0

V high = l.len - 1

Line 160:

Line 159:

R mid

R -1</syntaxhighlight>

=={{header|360 Assembly}}==

<syntaxhighlight lang=360asm>* Binary search 05/03/2017

<syntaxhighlight lang="360asm">* Binary search 05/03/2017

BINSEAR CSECT

USING BINSEAR,R13 base register

Line 238:

Line 236:

229 found at 23

</pre>

=={{header|8080 Assembly}}==

Line 247:

Line 244:

Test code is included, which will loop through the values [0..255] and report for each number whether it was in the array or not.

<syntaxhighlight lang=8080asm> org 100h ; Entry for test code

<syntaxhighlight lang="8080asm"> org 100h ; Entry for test code

jmp test

Line 352:

Line 349:

=={{header|AArch64 Assembly}}==

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program binSearch64.s */

Line 601:

Line 598:

Value find at index : 8

</pre>

=={{header|ACL2}}==

<syntaxhighlight lang=~~Lisp~~>(defun defarray (name size initial-element)

<syntaxhighlight lang="lisp">(defun defarray (name size initial-element)

(cons name

(compress1 name

Line 665:

Line 661:

(defarray 'haystack *dim* 0)

*dim*)))</syntaxhighlight>

=={{header|Action!}}==

<syntaxhighlight lang=~~Action~~!>INT FUNC BinarySearch(INT ARRAY a INT len,value)

<syntaxhighlight lang="action!">INT FUNC BinarySearch(INT ARRAY a INT len,value)

INT low,high,mid

Line 723:

Line 718:

[-6 0 1 2 5 6 8 9] 7 not found

</pre>

=={{header|Ada}}==

Both solutions are generic. The element can be of any comparable type (such that the operation < is visible in the instantiation scope of the function Search). Note that the completion condition is different from one given in the pseudocode example above. The example assumes that the array index type does not overflow when mid is incremented or decremented beyond the corresponding array bound. This is a wrong assumption for Ada, where array bounds can start or end at the very first or last value of the index type. To deal with this, the exit condition is rather directly expressed as crossing the corresponding array bound by the coming interval middle.

;Recursive:

<syntaxhighlight lang=ada>with Ada.Text_IO; use Ada.Text_IO;

<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Recursive_Binary_Search is

Line 782:

Line 776:

end Test_Recursive_Binary_Search;</syntaxhighlight>

;Iterative:

<syntaxhighlight lang=ada>with Ada.Text_IO; use Ada.Text_IO;

<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Binary_Search is

Line 847:

Line 841:

2 4 6 8 9 does not contain 5

</pre>

=={{header|ALGOL 68}}==

<syntaxhighlight lang=algol68>BEGIN

<syntaxhighlight lang="algol68">BEGIN

MODE ELEMENT = STRING;

Line 906:

Line 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 %

<syntaxhighlight lang="algolw">begin % binary search %

% recursive binary search, left most insertion point %

integer procedure binarySearchLR ( integer array A ( * )

Line 969:

Line 961:

iterative search suggests insert 24 at 5

</pre>

=={{header|APL}}==

<syntaxhighlight lang=~~APL~~>binsrch←{

<syntaxhighlight lang="apl">binsrch←{

⎕IO(⍺{ ⍝ first lower bound is start of array

⍵<⍺:⍬ ⍝ if high < low, we didn't find it

Line 983:

Line 974:

}

</syntaxhighlight>

=={{header|AppleScript}}==

<syntaxhighlight lang=applescript>on binarySearch(n, theList, l, r)

<syntaxhighlight lang="applescript">on binarySearch(n, theList, l, r)

repeat until (l = r)

set m to (l + r) div 2

Line 1,017:

Line 1,007:

The first occurrence of 7 in range 7 thru 12 of the list is at index 7

7 is not in range 1 thru 5 of the list"</pre>

=={{header|ARM Assembly}}==

/* ARM assembly Raspberry PI */

Line 1,298:

Line 1,287:

</syntaxhighlight>

=={{header|Arturo}}==

<syntaxhighlight lang=rebol>binarySearch: function [arr,val,low,high][

<syntaxhighlight lang="rebol">binarySearch: function [arr,val,low,high][

if high < low -> return ø

mid: shr low+high 1

Line 1,329:

Line 1,317:

found 24324 at index: 24

99999 not found</pre>

=={{header|AutoHotkey}}==

<syntaxhighlight lang=~~AutoHotkey~~>array := "1,2,4,6,8,9"

<syntaxhighlight lang="autohotkey">array := "1,2,4,6,8,9"

StringSplit, A, array, `, ; creates associative array

MsgBox % x := BinarySearch(A, 4, 1, A0) ; Recursive

Line 1,364:

Line 1,351:

Return not_found

}</syntaxhighlight>

=={{header|AWK}}==

Line 1,370:

Line 1,356:

'''Recursive'''

<syntaxhighlight lang=awk>function binary_search(array, value, left, right, middle) {

<syntaxhighlight lang="awk">function binary_search(array, value, left, right, middle) {

if (right < left) return 0

middle = int((right + left) / 2)

Line 1,379:

Line 1,365:

}</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=awk>function binary_search(array, value, left, right, middle) {

<syntaxhighlight lang="awk">function binary_search(array, value, left, right, middle) {

while (left <= right) {

middle = int((right + left) / 2)

Line 1,388:

Line 1,374:

return 0

}</syntaxhighlight>

=={{header|Axe}}==

'''Iterative'''

Line 1,394:

Line 1,379:

BSEARCH takes 3 arguments: a pointer to the start of the data, the data to find, and the length of the array in bytes.

<syntaxhighlight lang=axe>Lbl BSEARCH

<syntaxhighlight lang="axe">Lbl BSEARCH

0→L

r₃-1→H

Line 1,410:

Line 1,395:

-1

Return</syntaxhighlight>

=={{header|BASIC}}==

'''Recursive'''

<syntaxhighlight lang=freebasic>FUNCTION binary_search ( array() AS Integer, value AS Integer, lo AS Integer, hi AS Integer) AS Integer

<syntaxhighlight lang="freebasic">FUNCTION binary_search ( array() AS Integer, value AS Integer, lo AS Integer, hi AS Integer) AS Integer

DIM middle AS Integer

Line 1,435:

Line 1,419:

<syntaxhighlight lang=freebasic>FUNCTION binary_search ( array() AS Integer, value AS Integer, lo AS Integer, hi AS Integer) AS Integer

<syntaxhighlight lang="freebasic">FUNCTION binary_search ( array() AS Integer, value AS Integer, lo AS Integer, hi AS Integer) AS Integer

DIM middle AS Integer

Line 1,455:

Line 1,439:

The following program can be used to test both recursive and iterative version.

<syntaxhighlight lang=freebasic>SUB search (array() AS Integer, value AS Integer)

<syntaxhighlight lang="freebasic">SUB search (array() AS Integer, value AS Integer)

DIM idx AS Integer

Line 1,484:

Line 1,468:

==={{header|ASIC}}===

REM Binary search

DIM A(10)

Line 1,553:

Line 1,537:

==={{header|BBC BASIC}}===

<syntaxhighlight lang=bbcbasic> DIM array%(9)

<syntaxhighlight lang="bbcbasic"> DIM array%(9)

array%() = 7, 14, 21, 28, 35, 42, 49, 56, 63, 70

Line 1,578:

Line 1,562:

==={{header|FreeBASIC}}===

<syntaxhighlight lang=freebasic>function binsearch( array() as integer, target as integer ) as integer

<syntaxhighlight lang="freebasic">function binsearch( array() as integer, target as integer ) as integer

'returns the index of the target number, or -1 if it is not in the array

dim as uinteger lo = lbound(array), hi = ubound(array), md = (lo + hi)\2

Line 1,592:

Line 1,576:

==={{header|IS-BASIC}}===

<syntaxhighlight lang=IS-~~BASIC~~>100 PROGRAM "Search.bas"

<syntaxhighlight lang="is-basic">100 PROGRAM "Search.bas"

110 RANDOMIZE

120 NUMERIC ARR(1 TO 20)

Line 1,624:

Line 1,608:

10 REM Binary search

20 LET N = 10

Line 1,672:

Line 1,656:

680 RETURN

</syntaxhighlight>

=={{header|BASIC256}}==

====Recursive Solution====

<syntaxhighlight lang=~~BASIC256~~>function binarySearchR(array, valor, lb, ub)

<syntaxhighlight lang="basic256">function binarySearchR(array, valor, lb, ub)

if ub < lb then

return false

Line 1,687:

Line 1,670:

====Iterative Solution====

<syntaxhighlight lang=~~BASIC256~~>function binarySearchI(array, valor)

<syntaxhighlight lang="basic256">function binarySearchI(array, valor)

lb = array[?,]

ub = array[?]

Line 1,705:

Line 1,688:

end function</syntaxhighlight>

'''Test:'''

<syntaxhighlight lang=~~BASIC256~~>items = 10e5

<syntaxhighlight lang="basic256">items = 10e5

dim array(items)

for n = 0 to items-1 : array[n] = n : next n

Line 1,721:

Line 1,704:

3

50 millisec</pre>

=={{header|Batch File}}==

@echo off & setlocal enabledelayedexpansion

Line 1,773:

Line 1,755:

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 ← {

<syntaxhighlight lang="bqn">BSearch ← {

BS ⟨a, value⟩:

BS ⟨a, value, 0, ¯1+≠a⟩;

Line 1,792:

Line 1,773:

•Show BSearch ⟨8‿30‿35‿45‿49‿77‿79‿82‿87‿97, 97⟩</syntaxhighlight>

=={{header|Brat}}==

<syntaxhighlight lang=brat>binary_search = { search_array, value, low, high |

<syntaxhighlight lang="brat">binary_search = { search_array, value, low, high |

true? high < low

{ null }

Line 1,826:

Line 1,806:

{ p "Not found" }

{ p "Found at index: #{index}" }</syntaxhighlight>

=={{header|C}}==

<syntaxhighlight lang=c>#include <stdio.h>

<syntaxhighlight lang="c">#include <stdio.h>

int bsearch (int *a, int n, int x) {

Line 1,887:

Line 1,866:

5 is not found.

</pre>

=={{header|C sharp|C#}}==

'''Recursive'''

<syntaxhighlight lang=csharp>namespace Search {

<syntaxhighlight lang="csharp">namespace Search {

using System;

Line 1,962:

Line 1,940:

}</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=csharp>namespace Search {

<syntaxhighlight lang="csharp">namespace Search {

using System;

Line 2,036:

Line 2,014:

}</syntaxhighlight>

'''Example'''

<syntaxhighlight lang=csharp>//#define UseRecursiveSearch

<syntaxhighlight lang="csharp">//#define UseRecursiveSearch

using System;

Line 2,114:

Line 2,092:

glb = 13

lub = 21</pre>

=={{header|C++}}==

'''Recursive'''

template <class T> int binsearch(const T array[], int low, int high, T value) {

if (high < low) {

Line 2,145:

Line 2,122:

}</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=cpp>template <class T>

<syntaxhighlight lang="cpp">template <class T>

int binSearch(const T arr[], int len, T what) {

int low = 0;

Line 2,161:

Line 2,138:

}</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>

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>

<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>

<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>

<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>

<syntaxhighlight lang="cpp">bool found = std::binary_search(array, array+len, what); // a custom comparator can be given as fourth arg</syntaxhighlight>

=={{header|Chapel}}==

'''iterative''' -- almost a direct translation of the pseudocode

<syntaxhighlight lang=chapel>proc binsearch(A:[], value) {

<syntaxhighlight lang="chapel">proc binsearch(A:[], value) {

var low = A.domain.dim(1).low;

var high = A.domain.dim(1).high;

Line 2,199:

Line 2,175:

4

=={{header|Clojure}}==

'''Recursive'''

<syntaxhighlight lang=clojure>(defn bsearch

<syntaxhighlight lang="clojure">(defn bsearch

([coll t]

(bsearch coll 0 (dec (count coll)) t))

Line 2,218:

Line 2,193:

; so return its index

(= mth t) m)))))</syntaxhighlight>

=={{header|CLU}}==

<syntaxhighlight lang=clu>% Binary search in an array

<syntaxhighlight lang="clu">% Binary search in an array

% If the item is found, returns `true' and the index;

% if the item is not found, returns `false' and the leftmost insertion point

Line 2,288:

Line 2,262:

19 found at location 8

20 not found, would be inserted at location 9</pre>

=={{header|COBOL}}==

COBOL's <code>SEARCH ALL</code> statement is implemented as a binary search on most implementations.

<syntaxhighlight lang=cobol> >>SOURCE FREE

<syntaxhighlight lang="cobol"> >>SOURCE FREE

IDENTIFICATION DIVISION.

PROGRAM-ID. binary-search.

Line 2,309:

Line 2,282:

.

END PROGRAM binary-search.</syntaxhighlight>

=={{header|CoffeeScript}}==

'''Recursive'''

<syntaxhighlight lang=coffeescript>binarySearch = (xs, x) ->

<syntaxhighlight lang="coffeescript">binarySearch = (xs, x) ->

do recurse = (low = 0, high = xs.length - 1) ->

mid = Math.floor (low + high) / 2

Line 2,321:

Line 2,293:

else mid</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=coffeescript>binarySearch = (xs, x) ->

<syntaxhighlight lang="coffeescript">binarySearch = (xs, x) ->

[low, high] = [0, xs.length - 1]

while low <= high

Line 2,331:

Line 2,303:

NaN</syntaxhighlight>

'''Test'''

odds = (it for it in [1..n] by 2)

result = (it for it in \

Line 2,347:

Line 2,319:

4 is ordinal of 9

5 is ordinal of 11</pre>

=={{header|Common Lisp}}==

'''Iterative'''

<syntaxhighlight lang=lisp>(defun binary-search (value array)

<syntaxhighlight lang="lisp">(defun binary-search (value array)

(let ((low 0)

(high (1- (length array))))

Line 2,365:

Line 2,336:

(t (return middle)))))))</syntaxhighlight>

'''Recursive'''

<syntaxhighlight lang=lisp>(defun binary-search (value array &optional (low 0) (high (1- (length array))))

<syntaxhighlight lang="lisp">(defun binary-search (value array &optional (low 0) (high (1- (length array))))

(if (< high low)

nil

Line 2,377:

Line 2,348:

(t middle)))))</syntaxhighlight>

=={{header|Crystal}}==

'''Recursive'''

<syntaxhighlight lang=ruby>class Array

<syntaxhighlight lang="ruby">class Array

def binary_search(val, low = 0, high = (size - 1))

return nil if high < low

Line 2,406:

Line 2,376:

end</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=ruby>class Array

<syntaxhighlight lang="ruby">class Array

def binary_search_iterative(val)

low, high = 0, size - 1

Line 2,443:

Line 2,413:

99999 not found in array

</pre>

=={{header|D}}==

<syntaxhighlight lang=d>import std.stdio, std.array, std.range, std.traits;

<syntaxhighlight lang="d">import std.stdio, std.array, std.range, std.traits;

/// Recursive.

Line 2,495:

Line 2,464:

=={{header|Delphi}}==

See [[#Pascal]].

=={{header|E}}==

<syntaxhighlight lang=e>/** Returns null if the value is not found. */

<syntaxhighlight lang="e">/** Returns null if the value is not found. */

def binarySearch(collection, value) {

var low := 0

Line 2,511:

Line 2,479:

return null

}</syntaxhighlight>

=={{header|EasyLang}}==

<syntaxhighlight lang=text>func bin_search val . a[] res .

<syntaxhighlight lang="text">func bin_search val . a[] res .

low = 0

high = len a[] - 1

Line 2,531:

Line 2,498:

call bin_search 8 a[] r

print r</syntaxhighlight>

=={{header|Eiffel}}==

The following solution is based on the one described in: C. A. Furia, B. Meyer, and S. Velder. ''Loop Invariants: Analysis, Classification, and Examples''. ACM Computing Surveys, 46(3), Article 34, January 2014. (Also available at http://arxiv.org/abs/1211.4470). It includes detailed loop invariants and pre- and postconditions, which make the running time linear (instead of logarithmic) when full contract checking is enabled.

<syntaxhighlight lang=~~Eiffel~~>class

<syntaxhighlight lang="eiffel">class

APPLICATION

Line 2,656:

Line 2,622:

end</syntaxhighlight>

=={{header|Elixir}}==

<syntaxhighlight lang=elixir>defmodule Binary do

<syntaxhighlight lang="elixir">defmodule Binary do

def search(list, value), do: search(List.to_tuple(list), value, 0, length(list)-1)

Line 2,689:

Line 2,654:

99999 not found in list

</pre>

=={{header|Emacs Lisp}}==

(defun binary-search (value array)

(let ((low 0)

Line 2,702:

Line 2,666:

(setf low (1+ middle)))

(t (cl-return middle)))))))</syntaxhighlight>

=={{header|Erlang}}==

<syntaxhighlight lang=~~Erlang~~>%% Task: Binary Search algorithm

<syntaxhighlight lang="erlang">%% Task: Binary Search algorithm

%% Author: Abhay Jain

Line 2,731:

Line 2,694:

end

end.</syntaxhighlight>

=={{header|Euphoria}}==

===Recursive===

<syntaxhighlight lang=euphoria>function binary_search(sequence s, object val, integer low, integer high)

<syntaxhighlight lang="euphoria">function binary_search(sequence s, object val, integer low, integer high)

integer mid, cmp

if high < low then

Line 2,751:

Line 2,713:

end function</syntaxhighlight>

===Iterative===

<syntaxhighlight lang=euphoria>function binary_search(sequence s, object val)

<syntaxhighlight lang="euphoria">function binary_search(sequence s, object val)

integer low, high, mid, cmp

low = 1

Line 2,768:

Line 2,730:

return 0 -- not found

end function</syntaxhighlight>

=={{header|F Sharp|F#}}==

Generic recursive version, using #light syntax:

<syntaxhighlight lang=fsharp>let rec binarySearch (myArray:array<IComparable>, low:int, high:int, value:IComparable) =

<syntaxhighlight lang="fsharp">let rec binarySearch (myArray:array<IComparable>, low:int, high:int, value:IComparable) =

if (high < low) then

null

Line 2,783:

Line 2,744:

else

myArray.[mid]</syntaxhighlight>

=={{header|Factor}}==

Factor already includes a binary search in its standard library. The following code offers an interface compatible with the requirement of this task, and returns either the index of the element if it has been found or f otherwise.

<syntaxhighlight lang=factor>USING: binary-search kernel math.order ;

<syntaxhighlight lang="factor">USING: binary-search kernel math.order ;

: binary-search ( seq elt -- index/f )

[ [ <=> ] curry search ] keep = [ drop f ] unless ;</syntaxhighlight>

=={{header|FBSL}}==

FBSL has built-in QuickSort() and BSearch() functions:

<syntaxhighlight lang=qbasic>#APPTYPE CONSOLE

<syntaxhighlight lang="qbasic">#APPTYPE CONSOLE

DIM va[], sign = {1, -1}, toggle

Line 2,823:

Line 2,782:

'''Iterative:'''

<syntaxhighlight lang=qbasic>#APPTYPE CONSOLE

<syntaxhighlight lang="qbasic">#APPTYPE CONSOLE

DIM va[]

Line 2,858:

Line 2,817:

'''Recursive:'''

<syntaxhighlight lang=qbasic>#APPTYPE CONSOLE

<syntaxhighlight lang="qbasic">#APPTYPE CONSOLE

DIM va[]

Line 2,887:

Line 2,846:

Press any key to continue...</pre>

=={{header|Forth}}==

This version is designed for maintaining a sorted array. If the item is not found, then then location returned is the proper insertion point for the item. This could be used in an optimized [[Insertion sort]], for example.

<syntaxhighlight lang=forth>defer (compare)

<syntaxhighlight lang="forth">defer (compare)

' - is (compare) \ default to numbers

Line 2,921:

Line 2,879:

11 probe \ -1 11

12 probe \ 0 99</syntaxhighlight>

=={{header|Fortran}}==

'''Recursive'''

In ISO Fortran 90 or later use a RECURSIVE function and ARRAY SECTION argument:

<syntaxhighlight lang=fortran>recursive function binarySearch_R (a, value) result (bsresult)

<syntaxhighlight lang="fortran">recursive function binarySearch_R (a, value) result (bsresult)

real, intent(in) :: a(:), value

integer :: bsresult, mid

Line 2,946:

Line 2,903:

In ISO Fortran 90 or later use an ARRAY SECTION POINTER:

<syntaxhighlight lang=fortran>function binarySearch_I (a, value)

<syntaxhighlight lang="fortran">function binarySearch_I (a, value)

integer :: binarySearch_I

real, intent(in), target :: a(:)

Line 2,979:

Line 2,936:

The use of "exclusive" bounds simplifies the adjustment of the bounds: the appropriate bound simply receives the value of P, there is ''no'' + 1 or - 1 adjustment ''at every step''; similarly, the determination of an empty span is easy, and avoiding the risk of integer overflow via (L + R)/2 is achieved at the same time. The "inclusive" bounds version by contrast requires ''two'' manipulations of L and R ''at every step'' - once to see if the span is empty, and a second time to locate the index to test.

<syntaxhighlight lang=~~Fortran~~> INTEGER FUNCTION FINDI(X,A,N) !Binary chopper. Find i such that X = A(i)

<syntaxhighlight lang="fortran"> INTEGER FUNCTION FINDI(X,A,N) !Binary chopper. Find i such that X = A(i)

Careful: it is surprisingly difficult to make this neat, due to vexations when N = 0 or 1.

REAL X,A(*) !Where is X in array A(1:N)?

Line 3,010:

Line 2,967:

====An alternative version====

<syntaxhighlight lang=~~Fortran~~> INTEGER FUNCTION FINDI(X,A,N) !Binary chopper. Find i such that X = A(i)

<syntaxhighlight lang="fortran"> INTEGER FUNCTION FINDI(X,A,N) !Binary chopper. Find i such that X = A(i)

Careful: it is surprisingly difficult to make this neat, due to vexations when N = 0 or 1.

REAL X,A(*) !Where is X in array A(1:N)?

Line 3,044:

Line 3,001:

Incidentally, the exclusive-bounds version leads to a good version of the interpolation search (whereby the probe position is interpolated, not just in the middle of the span), unlike the version based on inclusive-bounds. Further, the unsourced offering in Wikipedia contains a bug - try searching an array of two equal elements for that value.

=={{header|Futhark}}==

{{incorrect|Futhark|Futhark's syntax has changed, so this example will not compile}}

Line 3,050:

Line 3,006:

Straightforward translation of imperative iterative algorithm.

fun main(as: [n]int, value: int): int =

let low = 0

Line 3,065:

Line 3,021:

in low

</syntaxhighlight>

=={{header|GAP}}==

<syntaxhighlight lang=gap>Find := function(v, x)

<syntaxhighlight lang="gap">Find := function(v, x)

local low, high, mid;

low := 1;

Line 3,090:

Line 3,045:

Find(u, 35);

# 5</syntaxhighlight>

=={{header|Go}}==

'''Recursive''':

<syntaxhighlight lang=go>func binarySearch(a []float64, value float64, low int, high int) int {

<syntaxhighlight lang="go">func binarySearch(a []float64, value float64, low int, high int) int {

if high < low {

return -1

Line 3,106:

Line 3,060:

}</syntaxhighlight>

'''Iterative''':

<syntaxhighlight lang=go>func binarySearch(a []float64, value float64) int {

<syntaxhighlight lang="go">func binarySearch(a []float64, value float64) int {

low := 0

high := len(a) - 1

Line 3,122:

Line 3,076:

}</syntaxhighlight>

'''Library''':

<syntaxhighlight lang=go>import "sort"

<syntaxhighlight lang="go">import "sort"

//...

Line 3,130:

Line 3,084:

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 3,151:

Line 3,104:

====Iterative Solution====

<syntaxhighlight lang=groovy>def binSearchI = { aList, target ->

<syntaxhighlight lang="groovy">def binSearchI = { aList, target ->

def a = aList

def offset = 0

Line 3,169:

Line 3,122:

}</syntaxhighlight>

Test:

<syntaxhighlight lang=groovy>def a = [] as Set

<syntaxhighlight lang="groovy">def a = [] as Set

def random = new Random()

while (a.size() < 20) { a << random.nextInt(30) }

Line 3,198:

Line 3,151:

Trial #5. Looking for: 32

Answer: [insertion point:20], : null</pre>

=={{header|Haskell}}==

===Recursive algorithm===

The algorithm itself, parametrized by an "interrogation" predicate ''p'' in the spirit of the explanation above:

<syntaxhighlight lang=haskell>import Data.Array (Array, Ix, (!), listArray, bounds)

<syntaxhighlight lang="haskell">import Data.Array (Array, Ix, (!), listArray, bounds)

-- BINARY SEARCH --------------------------------------------------------------

Line 3,261:

Line 3,213:

A common optimisation of recursion is to delegate the main computation to a helper function with simpler type signature. For the option type of the return value, we could also use an Either as an alternative to a Maybe.

<syntaxhighlight lang=haskell>import Data.Array (Array, Ix, (!), listArray, bounds)

<syntaxhighlight lang="haskell">import Data.Array (Array, Ix, (!), listArray, bounds)

-- BINARY SEARCH USING A HELPER FUNCTION WITH A SIMPLER TYPE SIGNATURE

Line 3,316:

Line 3,268:

It returns the result of applying '''f''' until '''p''' holds.

<syntaxhighlight lang=haskell>import Data.Array (Array, Ix, (!), listArray, bounds)

<syntaxhighlight lang="haskell">import Data.Array (Array, Ix, (!), listArray, bounds)

-- BINARY SEARCH USING THE ITERATIVE ALGORITHM

Line 3,368:

Line 3,320:

<pre>'kappa' found at index 7</pre>

=={{header|HicEst}}==

<syntaxhighlight lang=hicest>REAL :: n=10, array(n)

<syntaxhighlight lang="hicest">REAL :: n=10, array(n)

array = NINT( RAN(n) )

Line 3,402:

Line 3,353:

ENDDO

END</syntaxhighlight>

<syntaxhighlight lang=hicest>7 has position 9 in 0 0 1 2 3 3 4 6 7 8

<syntaxhighlight lang="hicest">7 has position 9 in 0 0 1 2 3 3 4 6 7 8

5 has position 0 in 0 0 1 2 3 3 4 6 7 8</syntaxhighlight>

=={{header|Hoon}}==

<syntaxhighlight lang=hoon>|= [arr=(list @ud) x=@ud]

<syntaxhighlight lang="hoon">|= [arr=(list @ud) x=@ud]

=/ lo=@ud 0

=/ hi=@ud (dec (lent arr))

Line 3,416:

Line 3,366:

?: (gth x val) $(lo +(mid))

mid</syntaxhighlight>

=={{header|Icon}} and {{header|Unicon}}==

Only a recursive solution is shown here.

<syntaxhighlight lang=icon>procedure binsearch(A, target)

<syntaxhighlight lang="icon">procedure binsearch(A, target)

if *A = 0 then fail

mid := *A/2 + 1

Line 3,431:

Line 3,380:

end</syntaxhighlight>

A program to test this is:

<syntaxhighlight lang=icon>procedure main(args)

<syntaxhighlight lang="icon">procedure main(args)

target := integer(!args) | 3

every put(A := [], 1 to 18 by 2)

Line 3,475:

Line 3,424:

->

</pre>

=={{header|J}}==

J already includes a binary search primitive (<code>I.</code>). The following code offers an interface compatible with the requirement of this task, and returns either the index of the element if it has been found or 'Not Found' otherwise:

<syntaxhighlight lang=j>bs=. i. 'Not Found'"_^:(-.@-:) I.</syntaxhighlight>

<syntaxhighlight lang="j">bs=. i. 'Not Found'"_^:(-.@-:) I.</syntaxhighlight>

'''Examples:'''

<syntaxhighlight lang=j> 2 3 5 6 8 10 11 15 19 20 bs 11

<syntaxhighlight lang="j"> 2 3 5 6 8 10 11 15 19 20 bs 11

6

2 3 5 6 8 10 11 15 19 20 bs 12

Line 3,487:

Line 3,435:

'''Iterative'''

<syntaxhighlight lang=j>'X Y L H M'=. i.5 NB. Setting mnemonics for boxes

<syntaxhighlight lang="j">'X Y L H M'=. i.5 NB. Setting mnemonics for boxes

f=. &({::) NB. Fetching the contents of a box

o=. @: NB. Composing verbs (functions)

Line 3,501:

Line 3,449:

bs=. return o (squeeze o midpoint ^: (L f <: H f) ^:_) o LowHigh o boxes</syntaxhighlight>

'''Recursive'''

<syntaxhighlight lang=j>'X Y L H M'=. i.5 NB. Setting mnemonics for boxes

<syntaxhighlight lang="j">'X Y L H M'=. i.5 NB. Setting mnemonics for boxes

f=. &({::) NB. Fetching the contents of a box

o=. @: NB. Composing verbs (functions)

Line 3,512:

Line 3,460:

bs=. (recur o midpoint`('Not Found'"_) @. (H f < L f) o boxes) :: ([ bs ] ; 0 ; (<: o # o [))</syntaxhighlight>

=={{header|Java}}==

'''Iterative'''

<syntaxhighlight lang=java>public class BinarySearchIterative {

<syntaxhighlight lang="java">public class BinarySearchIterative {

public static int binarySearch(int[] nums, int check) {

Line 3,547:

Line 3,494:

'''Recursive'''

<syntaxhighlight lang=java>public class BinarySearchRecursive {

<syntaxhighlight lang="java">public class BinarySearchRecursive {

public static int binarySearch(int[] haystack, int needle, int lo, int hi) {

Line 3,579:

Line 3,526:

For arrays:

<syntaxhighlight lang=java>import java.util.Arrays;

<syntaxhighlight lang="java">import java.util.Arrays;

int index = Arrays.binarySearch(array, thing);

Line 3,588:

Line 3,535:

int index = Arrays.binarySearch(array, startIndex, endIndex, thing, comparator);</syntaxhighlight>

For Lists:

<syntaxhighlight lang=java>import java.util.Collections;

<syntaxhighlight lang="java">import java.util.Collections;

int index = Collections.binarySearch(list, thing);

int index = Collections.binarySearch(list, thing, comparator);</syntaxhighlight>

=={{header|JavaScript}}==

===ES5===

Recursive binary search implementation

<syntaxhighlight lang=javascript>function binary_search_recursive(a, value, lo, hi) {

<syntaxhighlight lang="javascript">function binary_search_recursive(a, value, lo, hi) {

if (hi < lo) { return null; }

Line 3,610:

Line 3,556:

}</syntaxhighlight>

Iterative binary search implementation

<syntaxhighlight lang=javascript>function binary_search_iterative(a, value) {

<syntaxhighlight lang="javascript">function binary_search_iterative(a, value) {

var mid, lo = 0,

hi = a.length - 1;

Line 3,632:

Line 3,578:

Recursive and iterative, by composition of pure functions, with tests and output:

<syntaxhighlight lang=javascript>(() => {

<syntaxhighlight lang="javascript">(() => {

'use strict';

Line 3,829:

Line 3,775:

]

]</pre>

=={{header|jq}}==

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:<syntaxhighlight lang=jq>def binarySearch(value):

Recursive solution:<syntaxhighlight lang="jq">def binarySearch(value):

# To avoid copying the array, simply pass in the current low and high offsets

def binarySearch(low; high):

Line 3,844:

Line 3,789:

end;

binarySearch(0; length-1);</syntaxhighlight>

Example:<syntaxhighlight lang=jq>[-1,-1.1,1,1,null,[null]] | binarySearch(1)</syntaxhighlight>

Example:<syntaxhighlight lang="jq">[-1,-1.1,1,1,null,[null]] | binarySearch(1)</syntaxhighlight>

2

=={{header|Jsish}}==

<syntaxhighlight lang=javascript>/**

<syntaxhighlight lang="javascript">/**

Binary search, in Jsish, based on Javascript entry

Tectonics: jsish -u -time true -verbose true binarySearch.jsi

Line 3,912:

Line 3,856:

>

[PASS] binarySearch.jsi (165 ms)</pre>

=={{header|Julia}}==

'''Iterative''':

<syntaxhighlight lang=julia>function binarysearch(lst::Vector{T}, val::T) where T

<syntaxhighlight lang="julia">function binarysearch(lst::Vector{T}, val::T) where T

low = 1

high = length(lst)

Line 3,933:

Line 3,876:

'''Recursive''':

<syntaxhighlight lang=julia>function binarysearch(lst::Vector{T}, value::T, low=1, high=length(lst)) where T

<syntaxhighlight lang="julia">function binarysearch(lst::Vector{T}, value::T, low=1, high=length(lst)) where T

if isempty(lst) return 0 end

if low ≥ high

Line 3,951:

Line 3,894:

end

end</syntaxhighlight>

=={{header|K}}==

Recursive:

bs:{[a;t]

if[0=#a; :_n];

Line 3,970:

Line 3,912:

0 1 2 3 4 5 6 7 8 9

</syntaxhighlight>

=={{header|Kotlin}}==

<syntaxhighlight lang=scala>fun <T : Comparable<T>> Array<T>.iterativeBinarySearch(target: T): Int {

<syntaxhighlight lang="scala">fun <T : Comparable<T>> Array<T>.iterativeBinarySearch(target: T): Int {

var hi = size - 1

var lo = 0

Line 4,015:

Line 3,956:

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 4,048:

Line 3,988:

{BS {B} 12345} -> 12345 is at array[6172]

</syntaxhighlight>

=={{header|Liberty BASIC}}==

dim theArray(100)

for i = 1 to 100

Line 4,071:

Line 4,010:

END FUNCTION

</syntaxhighlight>

=={{header|Logo}}==

<syntaxhighlight lang=logo>to bsearch :value :a :lower :upper

<syntaxhighlight lang="logo">to bsearch :value :a :lower :upper

if :upper < :lower [output []]

localmake "mid int (:lower + :upper) / 2

Line 4,080:

Line 4,018:

output :mid

end</syntaxhighlight>

=={{header|Lolcode}}==

'''Iterative'''

HAI 1.2

CAN HAS STDIO?

Line 4,183:

Line 4,120:

I CAN HAS UR CHEEZBURGER NAO?

</pre>

=={{header|Lua}}==

'''Iterative'''

<syntaxhighlight lang=lua>function binarySearch (list,value)

<syntaxhighlight lang="lua">function binarySearch (list,value)

local low = 1

local high = #list

Line 4,199:

Line 4,135:

end</syntaxhighlight>

'''Recursive'''

<syntaxhighlight lang=lua>function binarySearch (list, value)

<syntaxhighlight lang="lua">function binarySearch (list, value)

local function search(low, high)

if low > high then return false end

Line 4,209:

Line 4,145:

return search(1,#list)

end</syntaxhighlight>

=={{header|M4}}==

<syntaxhighlight lang="m4">define(`notfound',`-1')dnl

define(`midsearch',`ifelse(defn($1[$4]),$2,$4,

`ifelse(eval(defn($1[$4])>$2),1,`binarysearch($1,$2,$3,decr($4))',`binarysearch($1,$2,incr($4),$5)')')')dnl

define(`binarysearch',`ifelse(eval($4<$3),1,notfound,`midsearch($1,$2,$3,eval(($3+$4)/2),$4)')')dnl

dnl

define(`setrange',`ifelse(`$3',`',$2,`define($1[$2],$3)`'setrange($1,incr($2),shift(shift(shift($@))))')')dnl

define(`asize',decr(setrange(`a',1,1,3,5,7,11,13,17,19,23,29)))dnl

dnl

binarysearch(`a',5,1,asize)

binarysearch(`a',8,1,asize)</syntaxhighlight>

Output:

<pre>

3

-1

</pre>

=={{header|M2000 Interpreter}}==

\\ binary search

const N=10

Line 4,258:

Line 4,209:

</syntaxhighlight>

=={{header|M4}}==

<syntaxhighlight lang=M4>define(`notfound',`-1')dnl

define(`midsearch',`ifelse(defn($1[$4]),$2,$4,

`ifelse(eval(defn($1[$4])>$2),1,`binarysearch($1,$2,$3,decr($4))',`binarysearch($1,$2,incr($4),$5)')')')dnl

define(`binarysearch',`ifelse(eval($4<$3),1,notfound,`midsearch($1,$2,$3,eval(($3+$4)/2),$4)')')dnl

dnl

define(`setrange',`ifelse(`$3',`',$2,`define($1[$2],$3)`'setrange($1,incr($2),shift(shift(shift($@))))')')dnl

define(`asize',decr(setrange(`a',1,1,3,5,7,11,13,17,19,23,29)))dnl

dnl

binarysearch(`a',5,1,asize)

binarysearch(`a',8,1,asize)</syntaxhighlight>

Output:

<pre>

3

-1

</pre>

=={{header|Maple}}==

The calculation of "mid" cannot overflow, since Maple uses arbitrary precision integer arithmetic, and the largest list or array is far, far smaller than the effective range of integers.

'''Recursive'''

<syntaxhighlight lang=~~Maple~~>BinarySearch := proc( A, value, low, high )

<syntaxhighlight lang="maple">BinarySearch := proc( A, value, low, high )

description "recursive binary search";

if high < low then

Line 4,297:

Line 4,230:

'''Iterative'''

<syntaxhighlight lang=~~Maple~~>BinarySearch := proc( A, value )

<syntaxhighlight lang="maple">BinarySearch := proc( A, value )

description "iterative binary search";

local low, high;

Line 4,315:

Line 4,248:

end proc:</syntaxhighlight>

We can use either lists or Arrays (or Vectors) for the first argument for these.

<syntaxhighlight lang=~~Maple~~>> N := 10:

<syntaxhighlight lang="maple">> N := 10:

> P := [seq]( ithprime( i ), i = 1 .. N ):

> BinarySearch( P, 12, 1, N ); # recursive version

Line 4,332:

Line 4,265:

> PP[ 3 ];

13</syntaxhighlight>

=={{header|Mathematica}} / {{header|Wolfram Language}}==

'''Recursive'''

<syntaxhighlight lang=~~Mathematica~~>BinarySearchRecursive[x_List, val_, lo_, hi_] :=

<syntaxhighlight lang="mathematica">BinarySearchRecursive[x_List, val_, lo_, hi_] :=

Module[{mid = lo + Round@((hi - lo)/2)},

If[hi < lo, Return[-1]];

Line 4,345:

Line 4,277:

]</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=~~Mathematica~~>BinarySearch[x_List, val_] := Module[{lo = 1, hi = Length@x, mid},

<syntaxhighlight lang="mathematica">BinarySearch[x_List, val_] := Module[{lo = 1, hi = Length@x, mid},

While[lo <= hi,

mid = lo + Round@((hi - lo)/2);

Line 4,355:

Line 4,287:

Return[-1];

]</syntaxhighlight>

=={{header|MATLAB}}==

'''Recursive'''

<syntaxhighlight lang=~~MATLAB~~>function mid = binarySearchRec(list,value,low,high)

<syntaxhighlight lang="matlab">function mid = binarySearchRec(list,value,low,high)

if( high < low )

Line 4,379:

Line 4,310:

end</syntaxhighlight>

Sample Usage:

<syntaxhighlight lang=~~MATLAB~~>>> binarySearchRec([1 2 3 4 5 6 6.5 7 8 9 11 18],6.5,1,numel([1 2 3 4 5 6 6.5 7 8 9 11 18]))

<syntaxhighlight lang="matlab">>> binarySearchRec([1 2 3 4 5 6 6.5 7 8 9 11 18],6.5,1,numel([1 2 3 4 5 6 6.5 7 8 9 11 18]))

ans =

Line 4,385:

Line 4,316:

7</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=~~MATLAB~~>function mid = binarySearchIter(list,value)

<syntaxhighlight lang="matlab">function mid = binarySearchIter(list,value)

low = 1;

Line 4,406:

Line 4,337:

end</syntaxhighlight>

Sample Usage:

<syntaxhighlight lang=~~MATLAB~~>>> binarySearchIter([1 2 3 4 5 6 6.5 7 8 9 11 18],6.5)

<syntaxhighlight lang="matlab">>> binarySearchIter([1 2 3 4 5 6 6.5 7 8 9 11 18],6.5)

ans =

7</syntaxhighlight>

=={{header|Maxima}}==

<syntaxhighlight lang=maxima>find(L, n) := block([i: 1, j: length(L), k, p],

<syntaxhighlight lang="maxima">find(L, n) := block([i: 1, j: length(L), k, p],

if n < L[i] or n > L[j] then 0 else (

while j - i > 0 do (

Line 4,433:

Line 4,363:

find(a, 421);

82</syntaxhighlight>

=={{header|MAXScript}}==

'''Iterative'''

<syntaxhighlight lang=maxscript>fn binarySearchIterative arr value =

<syntaxhighlight lang="maxscript">fn binarySearchIterative arr value =

(

lower = 1

Line 4,462:

Line 4,391:

result = binarySearchIterative arr 6</syntaxhighlight>

'''Recursive'''

<syntaxhighlight lang=maxscript>fn binarySearchRecursive arr value lower upper =

<syntaxhighlight lang="maxscript">fn binarySearchRecursive arr value lower upper =

(

if lower == upper then

Line 4,492:

Line 4,421:

arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10)

result = binarySearchRecursive arr 6 1 arr.count</syntaxhighlight>

=={{header|MiniScript}}==

'''Recursive:'''

<syntaxhighlight lang=~~MiniScript~~>binarySearch = function(A, value, low, high)

<syntaxhighlight lang="miniscript">binarySearch = function(A, value, low, high)

if high < low then return null

mid = floor((low + high) / 2)

Line 4,504:

Line 4,432:

'''Iterative:'''

<syntaxhighlight lang=~~MiniScript~~>binarySearch = function(A, value)

<syntaxhighlight lang="miniscript">binarySearch = function(A, value)

low = 0

high = A.len - 1

Line 4,519:

Line 4,447:

end while

end function</syntaxhighlight>

=={{header|N/t/roff}}==

<syntaxhighlight lang=text>.de end

<syntaxhighlight lang="text">.de end

..

.de array

Line 4,562:

Line 4,489:

.el The item \fBdoes exist\fP.

</syntaxhighlight>

=={{header|Nim}}==

'''Library'''

<syntaxhighlight lang=nim>import algorithm

<syntaxhighlight lang="nim">import algorithm

let s = @[2,3,4,5,6,7,8,9,10,12,14,16,18,20,22,25,27,30]

Line 4,571:

Line 4,497:

'''Iterative''' (from the standard library)

<syntaxhighlight lang=nim>proc binarySearch[T](a: openArray[T], key: T): int =

<syntaxhighlight lang="nim">proc binarySearch[T](a: openArray[T], key: T): int =

var b = len(a)

while result < b:

Line 4,578:

Line 4,504:

else: b = mid

if result >= len(a) or a[result] != key: result = -1</syntaxhighlight>

=={{header|Niue}}==

'''Library'''

<syntaxhighlight lang=ocaml>1 2 3 4 5

<syntaxhighlight lang="ocaml">1 2 3 4 5

3 bsearch . ( => 2 )

5 bsearch . ( => 0 )

Line 4,591:

Line 4,516:

'kenny bsearch . ( => 2 )

'tony bsearch . ( => -1)</syntaxhighlight>

=={{header|Objeck}}==

'''Iterative'''

<syntaxhighlight lang=objeck>use Structure;

<syntaxhighlight lang="objeck">use Structure;

bundle Default {

Line 4,626:

Line 4,550:

}

}</syntaxhighlight>

=={{header|Objective-C}}==

'''Iterative'''

<syntaxhighlight lang=objc>#import <Foundation/Foundation.h>

<syntaxhighlight lang="objc">#import <Foundation/Foundation.h>

@interface NSArray (BinarySearch)

Line 4,671:

Line 4,594:

}</syntaxhighlight>

'''Recursive'''

<syntaxhighlight lang=objc>#import <Foundation/Foundation.h>

<syntaxhighlight lang="objc">#import <Foundation/Foundation.h>

@interface NSArray (BinarySearchRecursive)

Line 4,711:

Line 4,634:

'''Library'''

<syntaxhighlight lang=objc>#import <Foundation/Foundation.h>

<syntaxhighlight lang="objc">#import <Foundation/Foundation.h>

int main()

Line 4,727:

Line 4,650:

}</syntaxhighlight>

Using Core Foundation (part of Cocoa, all versions):

<syntaxhighlight lang=objc>#import <Foundation/Foundation.h>

<syntaxhighlight lang="objc">#import <Foundation/Foundation.h>

CFComparisonResult myComparator(const void *x, const void *y, void *context) {

Line 4,746:

Line 4,669:

return 0;

}</syntaxhighlight>

=={{header|OCaml}}==

'''Recursive'''

<syntaxhighlight lang=ocaml>let rec binary_search a value low high =

<syntaxhighlight lang="ocaml">let rec binary_search a value low high =

if high = low then

if a.(low) = value then

Line 4,772:

Line 4,694:

</pre>

OCaml supports proper tail-recursion; so this is effectively the same as iteration.

=={{header|Octave}}==

'''Recursive'''

<syntaxhighlight lang=octave>function i = binsearch_r(array, val, low, high)

<syntaxhighlight lang="octave">function i = binsearch_r(array, val, low, high)

if ( high < low )

i = 0;

Line 4,790:

Line 4,711:

endfunction</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=octave>function i = binsearch(array, value)

<syntaxhighlight lang="octave">function i = binsearch(array, value)

low = 1;

high = numel(array);

Line 4,807:

Line 4,728:

endfunction</syntaxhighlight>

'''Example of using'''

<syntaxhighlight lang=octave>r = sort(discrete_rnd(10, [1:10], ones(10,1)/10));

<syntaxhighlight lang="octave">r = sort(discrete_rnd(10, [1:10], ones(10,1)/10));

disp(r);

binsearch_r(r, 5, 1, numel(r))

binsearch(r, 5)</syntaxhighlight>

=={{header|Ol}}==

(define (binary-search value vector)

(let helper ((low 0)

Line 4,830:

Line 4,750:

; ==> 12

</syntaxhighlight>

=={{header|ooRexx}}==

data = .array~of(1, 3, 5, 7, 9, 11)

-- search keys with a number of edge cases

Line 4,904:

Line 4,823:

Key 12 not found

</pre>

=={{header|Oz}}==

'''Recursive'''

<syntaxhighlight lang=oz>declare

<syntaxhighlight lang="oz">declare

fun {BinarySearch Arr Val}

fun {Search Low High}

Line 4,929:

Line 4,847:

{System.printInfo "searching 8: "} {Show {BinarySearch A 8}}</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=oz>declare

<syntaxhighlight lang="oz">declare

fun {BinarySearch Arr Val}

Low = {NewCell {Array.low Arr}}

Line 4,948:

Line 4,866:

{System.printInfo "searching 4: "} {Show {BinarySearch A 4}}

{System.printInfo "searching 8: "} {Show {BinarySearch A 8}}</syntaxhighlight>

=={{header|PARI/GP}}==

Note that, despite the name, <code>setsearch</code> works on sorted vectors as well as sets.

<syntaxhighlight lang=parigp>setsearch(s, n)</syntaxhighlight>

<syntaxhighlight lang="parigp">setsearch(s, n)</syntaxhighlight>

The following is another implementation that takes a more manual approach. Instead of using an intrinsic function, a general binary search algorithm is implemented using the language alone.

Line 4,957:

Line 4,874:

<syntaxhighlight lang=parigp>binarysearch(v, x) = {

<syntaxhighlight lang="parigp">binarysearch(v, x) = {

local(

minm = 1,

Line 4,981:

Line 4,898:

print("Item does not exist anywhere.") \

)</syntaxhighlight>

=={{header|Pascal}}==

'''Iterative'''

<syntaxhighlight lang=pascal>function binary_search(element: real; list: array of real): integer;

<syntaxhighlight lang="pascal">function binary_search(element: real; list: array of real): integer;

var

l, m, h: integer;

Line 5,010:

Line 4,926:

end;</syntaxhighlight>

Usage:

<syntaxhighlight lang=pascal>var

<syntaxhighlight lang="pascal">var

list: array[0 .. 9] of real;

// ...

indexof := binary_search(123, list);</syntaxhighlight>

=={{header|Perl}}==

'''Iterative'''

<syntaxhighlight lang=perl>sub binary_search {

<syntaxhighlight lang="perl">sub binary_search {

my ($array_ref, $value, $left, $right) = @_;

while ($left <= $right) {

Line 5,034:

Line 4,949:

}</syntaxhighlight>

'''Recursive'''

<syntaxhighlight lang=perl>sub binary_search {

<syntaxhighlight lang="perl">sub binary_search {

my ($array_ref, $value, $left, $right) = @_;

return -1 if ($right < $left);

Line 5,048:

Line 4,963:

}

}</syntaxhighlight>

=={{header|Phix}}==

Standard autoinclude builtin/bsearch.e, reproduced here (for reference only, don't copy/paste unless you plan to modify and rename it)

global function binary_search(object needle, sequence haystack)

integer lo = 1,

Line 5,076:

Line 4,990:

Returns a positive index if found, otherwise the negative index where it would go if inserted now. Example use

with javascript_semantics

?binary_search(0,{1,3,5}) -- -1

Line 5,086:

Line 5,000:

?binary_search(6,{1,3,5}) -- -4

=={{header|PHP}}==

'''Iterative'''

<syntaxhighlight lang=php>function binary_search( $array, $secret, $start, $end )

<syntaxhighlight lang="php">function binary_search( $array, $secret, $start, $end )

{

do

Line 5,109:

Line 5,022:

}</syntaxhighlight>

'''Recursive'''

<syntaxhighlight lang=php>function binary_search( $array, $secret, $start, $end )

<syntaxhighlight lang="php">function binary_search( $array, $secret, $start, $end )

{

$guess = (int)($start + ( ( $end - $start ) / 2 ));

Line 5,124:

Line 5,037:

return $guess;

}</syntaxhighlight>

=={{header|Picat}}==

===Iterative===

A = [2, 4, 6, 8, 9],

TestValues = [2,1,8,10,9,5],

Line 5,185:

Line 5,097:

===Recursive version===

<syntaxhighlight lang=~~Picat~~>binary_search_rec(A, Value) = Ret =>

<syntaxhighlight lang="picat">binary_search_rec(A, Value) = Ret =>

Ret = binary_search_rec(A,Value, 1, A.length).

Line 5,198:

Line 5,110:

end,

Mid = Mid1.</syntaxhighlight>

=={{header|PicoLisp}}==

'''Recursive'''

<syntaxhighlight lang=~~PicoLisp~~>(de recursiveSearch (Val Lst Len)

<syntaxhighlight lang="picolisp">(de recursiveSearch (Val Lst Len)

(unless (=0 Len)

(let (N (inc (/ Len 2)) L (nth Lst N))

Line 5,217:

Line 5,128:

-> NIL</pre>

'''Iterative'''

<syntaxhighlight lang=~~PicoLisp~~>(de iterativeSearch (Val Lst Len)

<syntaxhighlight lang="picolisp">(de iterativeSearch (Val Lst Len)

(use (N L)

(loop

Line 5,235:

Line 5,146:

: (iterativeSearch (9) (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9)

-> NIL</pre>

=={{header|PL/I}}==

<syntaxhighlight lang=PL/I>/* A binary search of list A for element M */

<syntaxhighlight lang="pl/i">/* A binary search of list A for element M */

search: procedure (A, M) returns (fixed binary);

declare (A(*), M) fixed binary;

Line 5,253:

Line 5,163:

return (lbound(A,1)-1);

end search;</syntaxhighlight>

=={{header|Pop11}}==

'''Iterative'''

<syntaxhighlight lang=pop11>define BinarySearch(A, value);

<syntaxhighlight lang="pop11">define BinarySearch(A, value);

lvars low = 1, high = length(A), mid;

while low <= high do

Line 5,278:

Line 5,187:

BinarySearch(A, 8) =></syntaxhighlight>

'''Recursive'''

<syntaxhighlight lang=pop11>define BinarySearch(A, value);

<syntaxhighlight lang="pop11">define BinarySearch(A, value);

define do_it(low, high);

if high < low then

Line 5,294:

Line 5,203:

do_it(1, length(A));

enddefine;</syntaxhighlight>

=={{header|PowerShell}}==

function BinarySearch-Iterative ([int[]]$Array, [int]$Value)

{

Line 5,364:

Line 5,272:

}

</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

Line 5,377:

Line 5,285:

Using BinarySearch-Recursive: 11 not found

</pre>

=={{header|Prolog}}==

Tested with Gnu-Prolog.

<syntaxhighlight lang=~~Prolog~~>bin_search(Elt,List,Result):-

<syntaxhighlight lang="prolog">bin_search(Elt,List,Result):-

length(List,N), bin_search_inner(Elt,List,1,N,Result).

Line 5,410:

Line 5,317:

?- bin_search(5,[1,2,4,8],Result).

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

<syntaxhighlight lang="purebasic">#Recursive = 0 ;recursive binary search method

#Iterative = 1 ;iterative binary search method

#NotFound = -1 ;search result if item not found

Line 5,512:

Line 5,418:

Value 20 found at index 9

</pre>

=={{header|Python}}==

===Python: Iterative===

<syntaxhighlight lang=python>def binary_search(l, value):

<syntaxhighlight lang="python">def binary_search(l, value):

low = 0

high = len(l)-1

Line 5,528:

Line 5,433:

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

<syntaxhighlight lang="python"># findIndexBinary :: (a -> Ordering) -> [a] -> Maybe Int

def findIndexBinary(p):

def isFound(bounds):

Line 5,624:

Line 5,529:

===Python: Recursive===

<syntaxhighlight lang=python>def binary_search(l, value, low = 0, high = -1):

<syntaxhighlight lang="python">def binary_search(l, value, low = 0, high = -1):

if not l: return -1

if(high == -1): high = len(l)-1

Line 5,639:

Line 5,544:

This time using the recursive definition:

<syntaxhighlight lang=python># findIndexBinary_ :: (a -> Ordering) -> [a] -> Maybe Int

<syntaxhighlight lang="python"># findIndexBinary_ :: (a -> Ordering) -> [a] -> Maybe Int

def findIndexBinary_(p):

def go(xs):

Line 5,713:

Line 5,618:

===Python: Library===

Python's <code>bisect</code> module provides binary search functions

<syntaxhighlight lang=python>index = bisect.bisect_left(list, item) # leftmost insertion point

<syntaxhighlight lang="python">index = bisect.bisect_left(list, item) # leftmost insertion point

index = bisect.bisect_right(list, item) # rightmost insertion point

index = bisect.bisect(list, item) # same as bisect_right

Line 5,725:

Line 5,630:

Complete binary search function with python's <code>bisect</code> module:

<syntaxhighlight lang=python>from bisect import bisect_left

<syntaxhighlight lang="python">from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None): # can't use a to specify default for hi

Line 5,734:

Line 5,639:

===Python: Approximate binary search===

Returns the nearest item of list l to value.

<syntaxhighlight lang=python>def binary_search(l, value):

<syntaxhighlight lang="python">def binary_search(l, value):

low = 0

high = len(l)-1

Line 5,746:

Line 5,651:

return mid

return high if abs(l[high] - value) < abs(l[low] - value) else low</syntaxhighlight>

=={{header|Quackery}}==

Written from pseudocode for rightmost insertion point, iterative.

<syntaxhighlight lang=~~Quackery~~> [ stack ] is value.bs ( --> n )

<syntaxhighlight lang="quackery"> [ stack ] is value.bs ( --> n )

[ stack ] is nest.bs ( --> n )

[ stack ] is test.bs ( --> n )

Line 5,794:

Line 5,698:

Stack empty.</pre>

=={{header|R}}==

'''Recursive'''

<syntaxhighlight lang=R>BinSearch <- function(A, value, low, high) {

<syntaxhighlight lang="r">BinSearch <- function(A, value, low, high) {

if ( high < low ) {

return(NULL)

Line 5,811:

Line 5,714:

}</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=R>IterBinSearch <- function(A, value) {

<syntaxhighlight lang="r">IterBinSearch <- function(A, value) {

low = 1

high = length(A)

Line 5,827:

Line 5,730:

}</syntaxhighlight>

'''Example'''

<syntaxhighlight lang=R>a <- 1:100

<syntaxhighlight lang="r">a <- 1:100

IterBinSearch(a, 50)

BinSearch(a, 50, 1, length(a)) # output 50

IterBinSearch(a, 101) # outputs NULL</syntaxhighlight>

=={{header|Racket}}==

#lang racket

(define (binary-search x v)

Line 5,853:

Line 5,755:

(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) {

<syntaxhighlight lang="raku" line>sub search (@a, $x --> Int) {

binary_search { $x cmp @a[$^i] }, 0, @a.end

}</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=raku line>sub binary_search (&p, Int $lo is copy, Int $hi is copy --> Int) {

<syntaxhighlight lang="raku" line>sub binary_search (&p, Int $lo is copy, Int $hi is copy --> Int) {

until $lo > $hi {

my Int $mid = ($lo + $hi) div 2;

Line 5,876:

Line 5,777:

<syntaxhighlight lang=raku line>sub binary_search (&p, Int $lo, Int $hi --> Int) {

<syntaxhighlight lang="raku" line>sub binary_search (&p, Int $lo, Int $hi --> Int) {

$lo <= $hi or fail;

my Int $mid = ($lo + $hi) div 2;

Line 5,885:

Line 5,786:

}

}</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.

(includes the extra credit)

<syntaxhighlight lang=rexx>/*REXX program finds a value in a list of integers using an iterative binary search.*/

<syntaxhighlight lang="rexx">/*REXX program finds a value in a list of integers using an iterative binary search.*/

@= 3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181,

193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401 409 421 433,

Line 5,933:

Line 5,833:

===iterative version===

(includes the extra credit)

<syntaxhighlight lang=rexx>/*REXX program finds a value in a list of integers using an iterative binary search.*/

<syntaxhighlight lang="rexx">/*REXX program finds a value in a list of integers using an iterative binary search.*/

@= 3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181,

193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401 409 421 433,

Line 5,970:

Line 5,870:

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]

Line 6,008:

Line 5,907:

the value 42 was found at index 6

</pre>

=={{header|Ruby}}==

'''Recursive'''

<syntaxhighlight lang=ruby>class Array

<syntaxhighlight lang="ruby">class Array

def binary_search(val, low=0, high=(length - 1))

return nil if high < low

Line 6,036:

Line 5,934:

end</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=ruby>class Array

<syntaxhighlight lang="ruby">class Array

def binary_search_iterative(val)

low, high = 0, length - 1

Line 6,074:

Line 5,972:

'''Built in'''

Since Ruby 2.0, arrays ship with a binary search method "bsearch":

<syntaxhighlight lang=ruby>haystack = [0,1,4,5,6,7,8,9,12,26,45,67,78,90,98,123,211,234,456,769,865,2345,3215,14345,24324]

<syntaxhighlight lang="ruby">haystack = [0,1,4,5,6,7,8,9,12,26,45,67,78,90,98,123,211,234,456,769,865,2345,3215,14345,24324]

needles = [0,42,45,24324,99999]

needles.select{|needle| haystack.bsearch{|hay| needle <=> hay} } # => [0, 45, 24324]

</syntaxhighlight>Which is 60% faster than "needles & haystack".

=={{header|Run BASIC}}==

'''Recursive'''

<syntaxhighlight lang=runbasic>dim theArray(100)

<syntaxhighlight lang="runbasic">dim theArray(100)

global theArray

for i = 1 to 100

Line 6,100:

Line 5,997:

END IF

END FUNCTION</syntaxhighlight>

=={{header|Rust}}==

'''Iterative'''

<syntaxhighlight lang=rust>fn binary_search<T:PartialOrd>(v: &[T], searchvalue: T) -> Option<T> {

<syntaxhighlight lang="rust">fn binary_search<T:PartialOrd>(v: &[T], searchvalue: T) -> Option<T> {

let mut lower = 0 as usize;

let mut upper = v.len() - 1;

Line 6,120:

Line 6,016:

None

}</syntaxhighlight>

=={{header|Scala}}==

'''Recursive'''

<syntaxhighlight lang=scala>def binarySearch[A <% Ordered[A]](a: IndexedSeq[A], v: A) = {

<syntaxhighlight lang="scala">def binarySearch[A <% Ordered[A]](a: IndexedSeq[A], v: A) = {

def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {

case _ if high < low => None

Line 6,133:

Line 6,028:

}</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=scala>def binarySearch[T](xs: Seq[T], x: T)(implicit ordering: Ordering[T]): Option[Int] = {

<syntaxhighlight lang="scala">def binarySearch[T](xs: Seq[T], x: T)(implicit ordering: Ordering[T]): Option[Int] = {

var low: Int = 0

var high: Int = xs.size - 1

Line 6,146:

Line 6,041:

}</syntaxhighlight>

'''Test'''

<syntaxhighlight lang=scala>def testBinarySearch(n: Int) = {

<syntaxhighlight lang="scala">def testBinarySearch(n: Int) = {

val odds = 1 to n by 2

val result = (0 to n).flatMap(binarySearch(odds, _))

Line 6,164:

Line 6,059:

4 is ordinal of 9

5 is ordinal of 11</pre>

=={{header|Scheme}}==

'''Recursive'''

<syntaxhighlight lang=scheme>(define (binary-search value vector)

<syntaxhighlight lang="scheme">(define (binary-search value vector)

(let helper ((low 0)

(high (- (vector-length vector) 1)))

Line 6,187:

Line 6,081:

The calls to helper are in tail position, so since Scheme implementations

support proper tail-recursion the computation proces is iterative.

=={{header|Seed7}}==

'''Iterative'''

<syntaxhighlight lang=seed7>const func integer: binarySearchIterative (in array elemType: arr, in elemType: aKey) is func

<syntaxhighlight lang="seed7">const func integer: binarySearchIterative (in array elemType: arr, in elemType: aKey) is func

result

var integer: result is 0;

Line 6,211:

Line 6,104:

end func;</syntaxhighlight>

'''Recursive'''

<syntaxhighlight lang=seed7>const func integer: binarySearch (in array elemType: arr, in elemType: aKey, in integer: low, in integer: high) is func

<syntaxhighlight lang="seed7">const func integer: binarySearch (in array elemType: arr, in elemType: aKey, in integer: low, in integer: high) is func

result

var integer: result is 0;

Line 6,227:

Line 6,120:

const func integer: binarySearchRecursive (in array elemType: arr, in elemType: aKey) is

return binarySearch(arr, aKey, 1, length(arr));</syntaxhighlight>

=={{header|SequenceL}}==

'''Recursive'''

<syntaxhighlight lang=sequencel>binarySearch(A(1), value(0), low(0), high(0)) :=

<syntaxhighlight lang="sequencel">binarySearch(A(1), value(0), low(0), high(0)) :=

let

mid := low + (high - low) / 2;

Line 6,241:

Line 6,133:

else

mid;</syntaxhighlight>

=={{header|Sidef}}==

Iterative:

<syntaxhighlight lang=ruby>func binary_search(a, i) {

<syntaxhighlight lang="ruby">func binary_search(a, i) {

var l = 0

Line 6,259:

Line 6,150:

}</syntaxhighlight>

Recursive:

<syntaxhighlight lang=ruby>func binary_search(arr, value, low=0, high=arr.end) {

<syntaxhighlight lang="ruby">func binary_search(arr, value, low=0, high=arr.end) {

high < low && return -1

var middle = ((high+low) // 2)

Line 6,277:

Line 6,168:

Usage:

<syntaxhighlight lang=ruby>say binary_search([34, 42, 55, 778], 55); #=> 2</syntaxhighlight>

<syntaxhighlight lang="ruby">say binary_search([34, 42, 55, 778], 55); #=> 2</syntaxhighlight>

=={{header|Simula}}==

<syntaxhighlight lang=simula>BEGIN

<syntaxhighlight lang="simula">BEGIN

Line 6,397:

Line 6,287:

</pre>

=={{header|SPARK}}==

SPARK does not allow recursion, so only the iterative solution is provided. This example shows the use of a loop assertion.

Line 6,408:

Line 6,297:

The first version has a postcondition that if Found is True the Position value returned is correct. This version also has a number of 'check' annotations. These are inserted to allow the Simplifier to prove all the verification conditions. See [[SPARK_Proof_Process|the SPARK Proof Process]].

<syntaxhighlight lang=~~Ada~~>package Binary_Searches is

<syntaxhighlight lang="ada">package Binary_Searches is

subtype Item_Type is Integer; -- From specs.

Line 6,506:

Line 6,395:

end Binary_Searches;</syntaxhighlight>

The second version of the package has a stronger postcondition on Search, which also states that if Found is False then there is no value in Source equal to Item. This postcondition cannot be proved without a precondition that Source is ordered. This version needs four user rules (see [[SPARK_Proof_Process|the SPARK Proof Process]]) to be provided to the Simplifier so that it can prove all the verification conditions.

<syntaxhighlight lang=~~Ada~~>package Binary_Searches is

<syntaxhighlight lang="ada">package Binary_Searches is

subtype Item_Type is Integer; -- From specs.

Line 6,628:

Line 6,517:

</pre>

The test program:

<syntaxhighlight lang=~~Ada~~>with Binary_Searches;

<syntaxhighlight lang="ada">with Binary_Searches;

with SPARK_IO;

Line 6,724:

Line 6,613:

Searching for 6 in ( 1 2 3 4 5 6 7 8 9): found as #96.

</pre>

=={{header|Standard ML}}==

'''Recursive'''

<syntaxhighlight lang=sml>fun binary_search cmp (key, arr) =

<syntaxhighlight lang="sml">fun binary_search cmp (key, arr) =

let

fun aux slice =

Line 6,782:

Line 6,670:

val it = SOME (4,8) : (int * IntArray.elem) option

</pre>

=={{header|Swift}}==

'''Recursive'''

<syntaxhighlight lang=swift>func binarySearch<T: Comparable>(xs: [T], x: T) -> Int? {

<syntaxhighlight lang="swift">func binarySearch<T: Comparable>(xs: [T], x: T) -> Int? {

var recurse: ((Int, Int) -> Int?)!

recurse = {(low, high) in switch (low + high) / 2 {

Line 6,796:

Line 6,683:

}</syntaxhighlight>

'''Iterative'''

<syntaxhighlight lang=swift>func binarySearch<T: Comparable>(xs: [T], x: T) -> Int? {

<syntaxhighlight lang="swift">func binarySearch<T: Comparable>(xs: [T], x: T) -> Int? {

var (low, high) = (0, xs.count - 1)

while low <= high {

Line 6,808:

Line 6,695:

}</syntaxhighlight>

'''Test'''

<syntaxhighlight lang=swift>func testBinarySearch(n: Int) {

<syntaxhighlight lang="swift">func testBinarySearch(n: Int) {

let odds = Array(stride(from: 1, through: n, by: 2))

let result = flatMap(0...n) {binarySearch(odds, $0)}

Line 6,831:

Line 6,718:

4 is ordinal of 9

5 is ordinal of 11</pre>

=={{header|Symsyn}}==

a : 1 : 2 : 27 : 44 : 46 : 57 : 77 : 154 : 212

Line 6,866:

Line 6,751:

</syntaxhighlight>

=={{header|Tcl}}==

ref: [http://wiki.tcl.tk/22796 Tcl wiki]

<syntaxhighlight lang=tcl>proc binSrch {lst x} {

<syntaxhighlight lang="tcl">proc binSrch {lst x} {

set len [llength $lst]

if {$len == 0} {

Line 6,895:

Line 6,779:

}</syntaxhighlight>

Note also that, from Tcl 8.4 onwards, the <tt>lsearch</tt> command includes the <tt>-sorted</tt> option to enable binary searching of Tcl lists.

<syntaxhighlight lang=tcl>proc binarySearch {lst x} {

<syntaxhighlight lang="tcl">proc binarySearch {lst x} {

set idx [lsearch -sorted -exact $lst $x]

if {$idx == -1} {

Line 6,903:

Line 6,787:

}

}</syntaxhighlight>

=={{header|TI-83 BASIC}}==

<syntaxhighlight lang=ti83b>PROGRAM:BINSEARC

<syntaxhighlight lang="ti83b">PROGRAM:BINSEARC

:Disp "INPUT A LIST:"

:Input L1

Line 6,932:

Line 6,815:

:Disp "IS NOT IN"

:Disp L1</syntaxhighlight>

=={{header|uBasic/4tH}}==

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

<syntaxhighlight lang="text">For i = 1 To 100 ' Fill array with some values

@(i-1) = i

Line 6,955:

Line 6,837:

If a@ = @(d@) Then Return (d@) ' We found it, return index!

EndIf</syntaxhighlight>

=={{header|UNIX Shell}}==

'''Reading values line by line'''

#!/bin/ksh

# This should work on any clone of Bourne Shell, ksh is the fastest.

Line 6,976:

Line 6,857:

'''Iterative'''

left=0

right=$(($size - 1))

Line 6,995:

Line 6,876:

'''Recursive'''

=={{header|UnixPipes}}==

'''Parallel'''

<syntaxhighlight lang=bash>splitter() {

<syntaxhighlight lang="bash">splitter() {

a=$1; s=$2; l=$3; r=$4;

mid=$(expr ${#a[*]} / 2);

Line 7,017:

Line 6,897:

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)

<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

Line 7,038:

Line 6,917:

End Function</syntaxhighlight>

Here are some test functions:

<syntaxhighlight lang=vb>Public Sub testBinarySearch(n)

<syntaxhighlight lang="vb">Public Sub testBinarySearch(n)

Dim a(1 To 100)

'create an array with values = multiples of 10

Line 7,068:

Line 6,947:

'''Iterative version:'''

<syntaxhighlight lang=vb>Public Function BinarySearch2(a, value)

<syntaxhighlight lang="vb">Public Function BinarySearch2(a, value)

'search for "value" in array a

'return index point if found, -1 if not found

Line 7,087:

Line 6,966:

BinarySearch2 = -1 'not found

End Function</syntaxhighlight>

=={{header|VBScript}}==

'''Recursive'''

<syntaxhighlight lang=vb>Function binary_search(arr,value,lo,hi)

<syntaxhighlight lang="vb">Function binary_search(arr,value,lo,hi)

If hi < lo Then

binary_search = 0

Line 7,130:

Line 7,008:

20 found at index 9

</pre>

=={{header|Vedit macro language}}==

'''Iterative'''

Line 7,136:

Line 7,013:

For this implementation, the numbers to be searched must be stored in current edit buffer, one number per line.

(Could be for example a csv table where the first column is used as key field.)

<syntaxhighlight lang=vedit>// Main program for testing BINARY_SEARCH

<syntaxhighlight lang="vedit">// Main program for testing BINARY_SEARCH

#3 = Get_Num("Value to search: ")

EOF

Line 7,166:

Line 7,043:

}

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

<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

Line 7,188:

Line 7,064:

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

<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

Line 7,205:

Line 7,081:

End If

End Function</syntaxhighlight>

=={{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

if high <= low {

return -1

Line 7,250:

Line 7,125:

-1

</pre>

=={{header|Wortel}}==

<syntaxhighlight lang=wortel>; Recursive

<syntaxhighlight lang="wortel">; Recursive

@var rec &[a v l h] [

@if < h l @return null

Line 7,277:

Line 7,151:

null

]</syntaxhighlight>

=={{header|Wren}}==

<syntaxhighlight lang=ecmascript>class BinarySearch {

<syntaxhighlight lang="ecmascript">class BinarySearch {

static recursive(a, value, low, high) {

if (high < low) return -1

Line 7,340:

Line 7,213:

70 was not found in the array.

</pre>

=={{header|XPL0}}==

\Binary search

code CrLf=9, IntOut=11, Text=12;

Line 7,410:

Line 7,282:

5 is not found.

</pre>

=={{header|Yabasic}}==

<syntaxhighlight lang=~~Yabasic~~>sub floor(n)

<syntaxhighlight lang="yabasic">sub floor(n)

return int(n + .5)

end sub

Line 7,445:

Line 7,316:

print binarySearch(list(), 3)

print peek("millisrunning")</syntaxhighlight>

=={{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

<syntaxhighlight lang="z/archasm">* Binary search

BINSRCH LA R5,TABLE Begin of table

SR R2,R2 low = 0

Line 7,465:

Line 7,335:

LOCRL R2,R1 Low? => LOW = MID+1

J LOOP }</syntaxhighlight>

=={{header|zkl}}==

This algorithm is tail recursive, which means it is both recursive and iterative (since tail recursion optimizes to a jump). Overflow is not possible because Ints (64 bit) are a lot bigger than the max length of a list.

<syntaxhighlight lang=zkl>fcn bsearch(list,value){ // list is sorted

<syntaxhighlight lang="zkl">fcn bsearch(list,value){ // list is sorted

fcn(list,value, low,high){

if (high < low) return(Void); // not found

Line 7,477:

Line 7,346:

}(list,value,0,list.len()-1);

}</syntaxhighlight>

<syntaxhighlight lang=zkl>list:=T(1,3,5,7,9,11); println("Sorted values: ",list);

<syntaxhighlight lang="zkl">list:=T(1,3,5,7,9,11); println("Sorted values: ",list);

foreach i in ([0..12]){

n:=bsearch(list,i);

Line 7,500:

Line 7,369:

Not found: 12

</pre>

=={{header|ZX Spectrum Basic}}==

Iterative method:

<syntaxhighlight lang=zxbasic>10 DATA 2,3,5,6,8,10,11,15,19,20

<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