Binary search: Difference between revisions

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.

 

As the player, an optimal strategy for the general case is to start by choosing the range's midpoint as the guess, and then asking whether the guess was higher, lower, or equal to the secret number. If the guess was too high, one would select the point exactly between the range midpoint and the beginning of the range. If the original guess was too low, one would ask about the point exactly between the range midpoint and the end of the range. This process repeats until one has reached the secret number.

 

 

Given the starting point of a range, the ending point of a range, and the "secret value", implement a binary search through a sorted integer array for a certain number. Implementations can be recursive or iterative (both if you can). Print out whether or not the number was in the array afterwards. If it was, print the index also.

 

* (for iterative algorithm) change <code>while (low <= high)</code> to <code>while (low < high)</code>

 

 

'''Recursive Pseudocode''':

}

 

The following algorithms return the leftmost place where the given element can be correctly inserted (and still maintain the sorted order). This is the lower (inclusive) bound of the range of elements that are equal to the given value (if any). Equivalently, this is the lowest index where the element is greater than or equal to the given value (since if it were any lower, it would violate the ordering), or 1 past the last index if such an element does not exist. This algorithm does not determine if the element is actually found. This algorithm only requires one comparison per level.

 

}

 

The following algorithms return the rightmost place where the given element can be correctly inserted (and still maintain the sorted order). This is the upper (exclusive) bound of the range of elements that are equal to the given value (if any). Equivalently, this is the lowest index where the element is greater than the given value, or 1 past the last index if such an element does not exist. This algorithm does not determine if the element is actually found. This algorithm only requires one comparison per level. Note that these algorithms are almost exactly the same as the leftmost-insertion-point algorithms, except for how the inequality treats equal values.

 

Make sure it does not have overflow bugs.

 

<pre>mid = (low + high) / 2</pre>

could produce the wrong result in some programming languages when used with a bounded integer type, if the addition causes an overflow. (This can occur if the array size is greater than half the maximum integer value.) If signed integers are used, and <code>low + high</code> overflows, it becomes a negative number, and dividing by 2 will still result in a negative number. Indexing an array with a negative number could produce an out-of-bounds exception, or other undefined behavior. If unsigned integers are used, an overflow will result in losing the largest bit, which will produce the wrong result.

where <code> >>> </code> is the logical right shift operator. The reason why this works is that, for signed integers, even though it overflows, when viewed as an unsigned number, the value is still the correct sum. To divide an unsigned number by 2, simply do a logical right shift.

 

:* [[wp:Binary search algorithm]]

:* [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|ACL2}}==

 

(cons name

(compress1 name

(populate-array-ordered

(defarray 'haystack *dim* 0)

 

=={{header|Ada}}==

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

;Recursive:

 

procedure Test_Recursive_Binary_Search is

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>

2 4 6 8 9 does not contain 5

</pre>

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

# Iterative: #

PROC iterative binary search = ([]ELEMENT hay stack, ELEMENT needle)INT: (

stop iteration:

out

# Recursive: #

PROC recursive binary search = ([]ELEMENT hay stack, ELEMENT needle)INT: (

[]ELEMENT hay stack = ("AA","Maestro","Mario","Master","Mattress","Mister","Mistress","ZZ"),

test cases = ("A","Master","Monk","ZZZ");

PROC test search = (PROC([]ELEMENT, ELEMENT)INT search, []ELEMENT test cases)VOID:

FOR case TO UPB test cases DO

INT index = search(hay stack, needle);

BOOL found = ( index <= 0 | FALSE | hay stack[index]=needle);

OD;

test search(iterative binary search, test cases);

test search(recursive binary search, test cases)

<pre>

"A" near index 1

"ZZZ" near index 8

</pre>

 

=={{header|AutoHotkey}}==

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

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

}

Return not_found

=={{header|AWK}}==

{{works with|Gawk}}

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

'''Iterative'''

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

Value 20 found at index 10

 

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

H% /= 2

UNTIL H%=0

 

=={{header|Brat}}==

true? high < low

{ null }

null? index

{ p "Not found" }

 

=={{header|C}}==

 

}

 

 

 

}

 

 

 

}

 

 

 

 

 

 

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

'''Recursive'''

}

 

{

int array[] = {2, 3, 5, 6, 8};

if (result1 == -1) std::cout << "4 not found!" << std::endl;

else std::cout << "4 found at " << result1 << std::endl;

 

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 mid = (low + high) / 2;

 

}

 

 

{{out}}

=={{header|Clojure}}==

'''Recursive'''

([coll t]

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

; we've found our target

; so return its index

 

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

4 is ordinal of 9

5 is ordinal of 11</pre>

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

'''Iterative'''

(let ((low 0)

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

(do () ((< high low) nil)

(cond ((> (aref array middle) value)

(setf low (1+ middle)))

'''Recursive'''

(if (< high low)

nil

(cond ((> (aref array middle) value)

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

 

=={{header|D}}==

 

/// Recursive.

// Standard Binary Search:

!items.equalRange(x).empty);

{{out}}

<pre> 1 false false false

5 false false false

2 true true true</pre>

=={{header|E}}==

def binarySearch(collection, value) {

var low := 0

}

return null

 

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

 

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

=={{header|Forth}}==

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

' - is (compare) \ default to numbers

 

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

 

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

 

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

 

It is because the method involves such a small amount of effort per iteration that minor changes offer a significant benefit. A lot depends on the implementation of the three-way test: the hope is that after the comparison, the computer hardware has indicators set for various outcomes, so that the necessary conditional branches can be made through successive inspection of those indicators, rather than repeating the comparison. These branch tests may in turn be made in an order that notes which option (if any) involves "falling through" to the next statement, thus it may be better to swap the order of labels 3 and 4. Further, the compiler may itself choose to re-order the various code pieces. First Fortran (in 1958) had a FREQUENCY statement whereby the programmer could indicate which paths were the more likely - for the binary search, equality is the less likely discovery. An assembler version of this routine attended to all these details.

else if expression < 0 then optionN

else optionZ;

if X > 0 then print "Positive"

else if X > 0 then print "Still positive";

That is, does the compiler make any remark, and does the resulting machine code contain a redundant test? However, despite all the above, the three-way IF statement has been declared deprecated in later versions of Fortran, with no alternative to repeated testing offered.

 

 

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

 

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 m = n.intdiv(2)

a.empty \

: a[m] < target \

: [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]

Trial #5. Looking for: 32

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

=={{header|Haskell}}==

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

| high < low = Nothing

 

The algorithm uses tail recursion, so the iterative and the recursive approach are identical in Haskell (the compiler will convert recursive calls into jumps).

 

=={{header|HicEst}}==

 

array = NINT( RAN(n) )

ENDIF

ENDDO

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

->

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

int hi = nums.length - 1;

int lo = 0;

}

return -1;

 

'''Recursive'''

 

}

int guess = (hi + lo) / 2;

}

return guess;

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

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;

 

=={{header|jq}}==

 

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

def binarySearch(low; high):

end

end;

{{Out}}

2

=={{header|Julia}}==

low = 1