Binary search: Difference between revisions

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

V low = 0

V high = l.len - 1

E

R mid

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

BINSEAR CSECT

USING BINSEAR,R13 base register

XDEC DS CL12 temp

YREGS

{{out}}

<pre>

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

rst 0

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

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program binSearch64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

<pre>

Value find at index : 0

=={{header|ACL2}}==

(cons name

(compress1 name

(populate-array-ordered

(defarray 'haystack *dim* 0)

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

INT low,high,mid

Test(a,8,10)

Test(a,8,7)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Binary_search.png Screenshot from Atari 8-bit computer]

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

Test ((2, 4, 6, 8, 9), 9);

Test ((2, 4, 6, 8, 9), 5);

;Iterative:

procedure Test_Binary_Search is

Test ((2, 4, 6, 8, 9), 9);

Test ((2, 4, 6, 8, 9), 5);

Sample output:

<pre>

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

MODE ELEMENT = STRING;

test search(recursive binary search, test cases)

)

{{out}}

Shows iterative search output - recursive search output is the same.

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

end for_s

end

{{out}}

<pre>

{{works with|Dyalog APL}}

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

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

}⍵)⎕IO+(≢⍺)-1 ⍝ first higher bound is top of array

}

=={{header|AppleScript}}==

repeat until (l = r)

set m to (l + r) div 2

set theList to {1, 2, 3, 3, 5, 7, 7, 8, 9, 10, 11, 12}

{{output}}

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

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

iMagicNumber: .int 0xCCCCCCCD

=={{header|Arturo}}==

if high < low -> return ø

mid: shr low+high 1

if? not? null? i -> print ["found" v "at index:" i]

else -> print [v "not found"]

{{out}}

=={{header|AutoHotkey}}==

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

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

}

Return not_found

=={{header|AWK}}==

{{works with|Nawk}}

'''Recursive'''

if (right < left) return 0

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

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)

}

return 0

=={{header|Axe}}==

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

End

-1

=={{header|BASIC}}==

{{works with|FreeBASIC}}

{{works with|RapidQ}}

DIM middle AS Integer

END SELECT

END IF

'''Iterative'''

{{works with|FreeBASIC}}

{{works with|RapidQ}}

DIM middle AS Integer

WEND

binary_search = 0

'''Testing the function'''

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

DIM idx AS Integer

search test(), 4

search test(), 8

Output:

Value 4 not found

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

REM Binary search

DIM A(10)

ENDIF

RETURN

{{out}}

<pre>

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

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

H% /= 2

UNTIL H%=0

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

wend

return -1

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

110 RANDOMIZE

120 NUMERIC ARR(1 TO 20)

340 LOOP WHILE BO<=UP AND T(K)<>N

350 IF BO<=UP THEN LET SEARCH=K

==={{header|Minimal BASIC}}===

{{works with|Commodore BASIC|3.5}}

{{works with|Nascom ROM BASIC|4.7}}

10 REM Binary search

20 LET N = 10

670 LET I1 = -1

680 RETURN

=={{header|BASIC256}}==

====Recursive Solution====

if ub < lb then

return false

if valor = array[mitad] then return mitad

end if

====Iterative Solution====

lb = array[?,]

ub = array[?]

end while

return false

'''Test:'''

dim array(items)

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

print binarySearchR(array, 3, array[?,], array[?])

print msec - t1; " millisec"

{{out}}

<pre>3

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

@echo off & setlocal enabledelayedexpansion

echo . binchop required !b! iterations

endlocal & exit /b 0

=={{header|BQN}}==

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

}

=={{header|Brat}}==

true? high < low

{ null }

null? index

{ p "Not found" }

=={{header|C}}==

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

return 0;

}

{{output}}

<pre>

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

'''Recursive'''

using System;

}

}

'''Iterative'''

using System;

}

}

'''Example'''

using System;

#endif

}

'''Output'''

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

'''Recursive'''

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

if (high < low) {

return 0;

'''Iterative'''

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

int low = 0;

}

return -1; // indicate not found

'''Library'''

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;

}

{{out}}

=={{header|Clojure}}==

'''Recursive'''

([coll t]

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

; we've found our target

; so return its index

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

end

end

{{out}}

<pre>1 not found, would be inserted at location 1

=={{header|COBOL}}==

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

IDENTIFICATION DIVISION.

PROGRAM-ID. binary-search.

END-SEARCH

.

=={{header|CoffeeScript}}==

'''Recursive'''

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

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

when xs[mid] > x then recurse low, mid - 1

when xs[mid] < x then recurse mid + 1, high

'''Iterative'''

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

while low <= high

when xs[mid] < x then low = mid + 1

else return mid

'''Test'''

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

result = (it for it in \

console.assert "#{result}" is "#{[0...odds.length]}"

console.log "#{odds} are odd natural numbers"

Output:

<pre>1,3,5,7,9,11 are odd natural numbers"

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

'''Iterative'''

(let ((low 0)

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

(setf low (1+ middle)))

'''Recursive'''

(if (< high low)

nil

(binary-search value array (1+ middle) high))

=={{header|Crystal}}==

'''Recursive'''

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

return nil if high < low

puts "#{val} not found in array"

end

'''Iterative'''

def binary_search_iterative(val)

low, high = 0, size - 1

puts "#{val} not found in array"

end

{{out}}

<pre>

=={{header|D}}==

/// Recursive.

// Standard Binary Search:

!items.equalRange(x).empty);

{{out}}

<pre> 1 false false false

=={{header|E}}==

def binarySearch(collection, value) {

var low := 0

}

return null

=={{header|EasyLang}}==

low = 0

high = len a[] - 1

a[] = [ 2 4 6 8 9 ]

call bin_search 8 a[] r

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

APPLICATION

end

=={{header|Elixir}}==

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

index -> IO.puts "found #{val} at index #{index}"

end

{{out}}

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

(defun binary-search (value array)

(let ((low 0)

((< (aref array middle) value)

(setf low (1+ middle)))

=={{header|Erlang}}==

%% Author: Abhay Jain

Mid

end

=={{header|Euphoria}}==

===Recursive===

integer mid, cmp

if high < low then

end if

end if

===Iterative===

integer low, high, mid, cmp

low = 1

end while

return 0 -- not found

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

Generic recursive version, using #light syntax:

if (high < low) then

null

binarySearch (myArray, mid+1, high, value)

else

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

=={{header|FBSL}}==

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

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

" in ", GetTickCount() - gtc, " milliseconds"

Output:<pre>Loading ... done in 906 milliseconds

Sorting ... done in 547 milliseconds

'''Iterative:'''

DIM va[]

WEND

RETURN -1

Output:<pre>Loading ... done in 391 milliseconds

3141592.65358979 found at index 1000000 in 62 milliseconds

'''Recursive:'''

DIM va[]

END IF

RETURN midp

Output:<pre>Loading ... done in 390 milliseconds

3141592.65358979 found at index 1000000 in 938 milliseconds

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

10 probe \ 0 11

11 probe \ -1 11

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

bsresult = mid ! SUCCESS!!

end if

'''Iterative'''

<br>

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

integer :: binarySearch_I

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

end if

end do

===Iterative, exclusive bounds, three-way test.===

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

Curse it!

5 FINDI = -L !X is not found. Insert it at L + 1, i.e. at A(1 - FINDI).

[[File:BinarySearch.Flowchart.png]]

====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)?

Curse it!

5 FINDI = -L !X is not found. Insert it at L + 1, i.e. at A(1 - FINDI).

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

Straightforward translation of imperative iterative algorithm.

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

let low = 0

else (mid, mid-1) -- Force termination.

in low

=={{header|GAP}}==

local low, high, mid;

low := 1;

# fail

Find(u, 35);

=={{header|Go}}==

'''Recursive''':

if high < low {

return -1

}

return mid

'''Iterative''':

low := 0

high := len(a) - 1

}

return -1

'''Library''':

//...

Exploration of library source code shows that it uses the <tt>mid = low + (high - low) / 2</tt> technique to avoid overflow.

Both solutions use ''sublists'' and a tracking offset in preference to "high" and "low".

====Recursive Solution====

def binSearchR

//define binSearchR closure.

: [index: offset + m]

}

====Iterative Solution====

def a = aList

def offset = 0

}

return ["insertion point": offset]

Test:

def random = new Random()

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

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]

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

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

case found of

Nothing -> "' Not found"

{{Out}}

<pre>'mu' found at index 9</pre>

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

("' " ++)

(("' found at index " ++) . show)

{{Out}}

<pre>'lambda' found at index 8</pre>

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

-- BINARY SEARCH USING THE ITERATIVE ALGORITHM

("' " ++)

(("' found at index " ++) . show)

{{Out}}

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

=={{header|HicEst}}==

array = NINT( RAN(n) )

ENDIF

ENDDO

=={{header|Hoon}}==

=/ lo=@ud 0

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

?: (lth x val) $(hi (dec mid))

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

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

Only a recursive solution is shown here.

if *A = 0 then fail

mid := *A/2 + 1

}

return mid

A program to test this is:

target := integer(!args) | 3

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

every writes(!A," ")

write()

with some sample runs:

<pre>

=={{header|J}}==

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

'''Examples:'''

6

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

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)

return=. (M f) o ((<@:('Not Found'"_) M} ]) ^: (_ ~: L f))

'''Recursive'''

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

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

recur=. (X f bs Y f ; L f ; (_1 + M f))`(M f)`(X f bs Y f ; (1 + M f) ; H f)@.case

=={{header|Java}}==

'''Iterative'''

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

}

}

'''Recursive'''

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

}

}

'''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);

// for objects, also optionally accepts an additional comparator argument:

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

For Lists:

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

=={{header|JavaScript}}==

===ES5===

Recursive binary search implementation

if (hi < lo) { return null; }

}

return mid;

Iterative binary search implementation

var mid, lo = 0,

hi = a.length - 1;

}

return null;

===ES6===

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

'use strict';

// MAIN ---

return main();

{{Out}}

<pre>[

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.

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

def binarySearch(low; high):

end

end;

{{Out}}

2

=={{header|Jsish}}==

Binary search, in Jsish, based on Javascript entry

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

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

{{works with|Julia|0.6}}

'''Iterative''':

low = 1

high = length(lst)

end

return 0

'''Recursive''':

if isempty(lst) return 0 end

if low ≥ high

return mid

end

=={{header|K}}==

Recursive:

bs:{[a;t]

if[0=#a; :_n];

{bs[v;x]}' v

0 1 2 3 4 5 6 7 8 9

=={{header|Kotlin}}==

var hi = size - 1

var lo = 0

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

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

{BS {B} 100} -> 100 is not found

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

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

dim theArray(100)

for i = 1 to 100

END IF

END FUNCTION

=={{header|Logo}}==

if :upper < :lower [output []]

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

if item :mid :a < :value [output bsearch :value :a :mid+1 :upper]

output :mid

=={{header|Lolcode}}==

'''Iterative'''

HAI 1.2

CAN HAS STDIO?

KTHXBYE

Output

<pre>

=={{header|Lua}}==

'''Iterative'''

local low = 1

local high = #list

end

return false

'''Recursive'''

local function search(low, high)

if low > high then return false end

end

return search(1,#list)

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

\\ binary search

const N=10

Print A()

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

dnl

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

Output:

<pre>

'''Recursive'''

description "recursive binary search";

if high < low then

end if

end if

'''Iterative'''

description "iterative binary search";

local low, high;

end do;

FAIL