Binary search: Difference between revisions
→{{header|Java}}: changed calculation of average - adding lo + hi, then dividing by two causes an overflow error with numbers close to Integer.MAX_VALUE |
added invariants |
||
Line 24: | Line 24: | ||
// initially called with low = 0, high = N-1 |
// initially called with low = 0, high = N-1 |
||
BinarySearch(A[0..N-1], value, low, high) { |
BinarySearch(A[0..N-1], value, low, high) { |
||
// invariants: value > A[i] for all i < low |
|||
value < A[i] for all i > high |
|||
if (high < low) |
if (high < low) |
||
return not_found // value would be inserted at index "low" |
return not_found // value would be inserted at index "low" |
||
Line 40: | Line 42: | ||
high = N - 1 |
high = N - 1 |
||
while (low <= high) { |
while (low <= high) { |
||
// invariants: value > A[i] for all i < low |
|||
value < A[i] for all i > high |
|||
mid = (low + high) / 2 |
mid = (low + high) / 2 |
||
if (A[mid] > value) |
if (A[mid] > value) |
||
Line 57: | Line 61: | ||
// initially called with low = 0, high = N - 1 |
// initially called with low = 0, high = N - 1 |
||
BinarySearch_Left(A[0..N-1], value, low, high) { |
BinarySearch_Left(A[0..N-1], value, low, high) { |
||
// invariants: value > A[i] for all i < low |
|||
value <= A[i] for all i > high |
|||
if (high < low) |
if (high < low) |
||
return low |
return low |
||
Line 71: | Line 77: | ||
high = N - 1 |
high = N - 1 |
||
while (low <= high) { |
while (low <= high) { |
||
// invariants: value > A[i] for all i < low |
|||
value <= A[i] for all i > high |
|||
mid = (low + high) / 2 |
mid = (low + high) / 2 |
||
if (A[mid] >= value) |
if (A[mid] >= value) |
||
Line 86: | Line 94: | ||
// initially called with low = 0, high = N - 1 |
// initially called with low = 0, high = N - 1 |
||
BinarySearch_Right(A[0..N-1], value, low, high) { |
BinarySearch_Right(A[0..N-1], value, low, high) { |
||
// invariants: value >= A[i] for all i < low |
|||
value < A[i] for all i > high |
|||
if (high < low) |
if (high < low) |
||
return low |
return low |
||
Line 100: | Line 110: | ||
high = N - 1 |
high = N - 1 |
||
while (low <= high) { |
while (low <= high) { |
||
// invariants: value >= A[i] for all i < low |
|||
value < A[i] for all i > high |
|||
mid = (low + high) / 2 |
mid = (low + high) / 2 |
||
if (A[mid] > value) |
if (A[mid] > value) |
Revision as of 21:03, 21 April 2011
You are encouraged to solve this task according to the task description, using any language you may know.
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 an analogy, consider the children's game "guess a number." The scorer has a secret number, and will only tell the player if their guessed number is higher than, lower than, or equal to the secret number. The player then uses this information to guess a new number.
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.
The Task
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.
There are several binary sort algorithms commonly seen. They differ by how they treat multiple values equal to the given value, and whether they indicate whether the element was found or not. For completeness we will present pseudocode for all of them.
All of the following code examples use an "inclusive" upper bound (i.e. high = N-1
initially). Any of the examples can be converted into an equivalent example using "exclusive" upper bound (i.e. high = N
initially) by making the following simple changes (which simply increase high
by 1):
- change
high = N-1
tohigh = N
- change
high = mid-1
tohigh = mid
- (for recursive algorithm) change
if (high < low)
toif (high <= low)
- (for iterative algorithm) change
while (low <= high)
towhile (low < high)
- Traditional algorithm
The algorithms are as follows (from Wikipedia). The algorithms return the index of some element that equals the given value (if there are multiple such elements, it returns some arbitrary one). It is also possible, when the element is not found, to return the "insertion point" for it (the index that the value would have if it were inserted into the array).
Recursive Pseudocode:
// initially called with low = 0, high = N-1 BinarySearch(A[0..N-1], value, low, high) { // invariants: value > A[i] for all i < low value < A[i] for all i > high if (high < low) return not_found // value would be inserted at index "low" mid = (low + high) / 2 if (A[mid] > value) return BinarySearch(A, value, low, mid-1) else if (A[mid] < value) return BinarySearch(A, value, mid+1, high) else return mid }
Iterative Pseudocode:
BinarySearch(A[0..N-1], value) { low = 0 high = N - 1 while (low <= high) { // invariants: value > A[i] for all i < low value < A[i] for all i > high mid = (low + high) / 2 if (A[mid] > value) high = mid - 1 else if (A[mid] < value) low = mid + 1 else return mid } return not_found // value would be inserted at index "low" }
- Leftmost insertion point
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.
Recursive Pseudocode:
// initially called with low = 0, high = N - 1 BinarySearch_Left(A[0..N-1], value, low, high) { // invariants: value > A[i] for all i < low value <= A[i] for all i > high if (high < low) return low mid = (low + high) / 2 if (A[mid] >= value) return BinarySearch_Left(A, value, low, mid-1) else return BinarySearch_Left(A, value, mid+1, high) }
Iterative Pseudocode:
BinarySearch_Left(A[0..N-1], value) { low = 0 high = N - 1 while (low <= high) { // invariants: value > A[i] for all i < low value <= A[i] for all i > high mid = (low + high) / 2 if (A[mid] >= value) high = mid - 1 else low = mid + 1 } return low }
- Rightmost insertion point
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.
Recursive Pseudocode:
// initially called with low = 0, high = N - 1 BinarySearch_Right(A[0..N-1], value, low, high) { // invariants: value >= A[i] for all i < low value < A[i] for all i > high if (high < low) return low mid = (low + high) / 2 if (A[mid] > value) return BinarySearch_Right(A, value, low, mid-1) else return BinarySearch_Right(A, value, mid+1, high) }
Iterative Pseudocode:
BinarySearch_Right(A[0..N-1], value) { low = 0 high = N - 1 while (low <= high) { // invariants: value >= A[i] for all i < low value < A[i] for all i > high mid = (low + high) / 2 if (A[mid] > value) high = mid - 1 else low = mid + 1 } return low }
- Extra credit
Make sure it does not have overflow bugs.
The line in the pseudocode above to calculate the mean of two integers:
mid = (low + high) / 2
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 low + high
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.
One way to fix it is to manually add half the range to the low number:
mid = low + (high - low) / 2
Even though this is mathematically equivalent to the above, it is not susceptible to overflow.
Another way for signed integers, possibly faster, is the following:
mid = (low + high) >>> 1
where >>>
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 to the right.
References:
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 <lang ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Recursive_Binary_Search is
Not_Found : exception; generic type Index is range <>; type Element is private; type Array_Of_Elements is array (Index range <>) of Element; with function "<" (L, R : Element) return Boolean is <>; function Search (Container : Array_Of_Elements; Value : Element) return Index;
function Search (Container : Array_Of_Elements; Value : Element) return Index is Mid : Index; begin if Container'Length > 0 then Mid := (Container'First + Container'Last) / 2; if Value < Container (Mid) then if Container'First /= Mid then return Search (Container (Container'First..Mid - 1), Value); end if; elsif Container (Mid) < Value then if Container'Last /= Mid then return Search (Container (Mid + 1..Container'Last), Value); end if; else return Mid; end if; end if; raise Not_Found; end Search;
type Integer_Array is array (Positive range <>) of Integer; function Find is new Search (Positive, Integer, Integer_Array); procedure Test (X : Integer_Array; E : Integer) is begin New_Line; for I in X'Range loop Put (Integer'Image (X (I))); end loop; Put (" contains" & Integer'Image (E) & " at" & Integer'Image (Find (X, E))); exception when Not_Found => Put (" does not contain" & Integer'Image (E)); end Test;
begin
Test ((2, 4, 6, 8, 9), 2); Test ((2, 4, 6, 8, 9), 1); Test ((2, 4, 6, 8, 9), 8); Test ((2, 4, 6, 8, 9), 10); Test ((2, 4, 6, 8, 9), 9); Test ((2, 4, 6, 8, 9), 5);
end Test_Recursive_Binary_Search;</lang> Iterative <lang ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Binary_Search is
Not_Found : exception; generic type Index is range <>; type Element is private; type Array_Of_Elements is array (Index range <>) of Element; with function "<" (L, R : Element) return Boolean is <>; function Search (Container : Array_Of_Elements; Value : Element) return Index;
function Search (Container : Array_Of_Elements; Value : Element) return Index is Low : Index := Container'First; High : Index := Container'Last; Mid : Index; begin if Container'Length > 0 then loop Mid := (Low + High) / 2; if Value < Container (Mid) then exit when Low = Mid; High := Mid - 1; elsif Container (Mid) < Value then exit when High = Mid; Low := Mid + 1; else return Mid; end if; end loop; end if; raise Not_Found; end Search;
type Integer_Array is array (Positive range <>) of Integer; function Find is new Search (Positive, Integer, Integer_Array); procedure Test (X : Integer_Array; E : Integer) is begin New_Line; for I in X'Range loop Put (Integer'Image (X (I))); end loop; Put (" contains" & Integer'Image (E) & " at" & Integer'Image (Find (X, E))); exception when Not_Found => Put (" does not contain" & Integer'Image (E)); end Test;
begin
Test ((2, 4, 6, 8, 9), 2); Test ((2, 4, 6, 8, 9), 1); Test ((2, 4, 6, 8, 9), 8); Test ((2, 4, 6, 8, 9), 10); Test ((2, 4, 6, 8, 9), 9); Test ((2, 4, 6, 8, 9), 5);
end Test_Binary_Search;</lang> Sample output:
2 4 6 8 9 contains 2 at 1 2 4 6 8 9 does not contain 1 2 4 6 8 9 contains 8 at 4 2 4 6 8 9 does not contain 10 2 4 6 8 9 contains 9 at 5 2 4 6 8 9 does not contain 5
ALGOL 68
<lang algol68>MODE ELEMENT = STRING;
- Iterative: #
PROC iterative binary search = ([]ELEMENT hay stack, ELEMENT needle)INT: (
INT out, low := LWB hay stack, high := UPB hay stack; WHILE low < high DO INT mid := (low+high) OVER 2; IF hay stack[mid] > needle THEN high := mid-1 ELIF hay stack[mid] < needle THEN low := mid+1 ELSE out:= mid; stop iteration FI OD; low EXIT stop iteration: out
- Recursive: #
PROC recursive binary search = ([]ELEMENT hay stack, ELEMENT needle)INT: (
IF LWB hay stack > UPB hay stack THEN LWB hay stack ELIF LWB hay stack = UPB hay stack THEN IF hay stack[LWB hay stack] = needle THEN LWB hay stack ELSE LWB hay stack FI ELSE INT mid := (LWB hay stack+UPB hay stack) OVER 2; IF hay stack[mid] > needle THEN recursive binary search(hay stack[:mid-1], needle) ELIF hay stack[mid] < needle THEN mid + recursive binary search(hay stack[mid+1:], needle) ELSE mid FI FI
);
- Test cases: #
test:(
ELEMENT needle = "mister"; []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 ELEMENT needle = test cases[case]; INT index = search(hay stack, needle); BOOL found = ( index <= 0 | FALSE | hay stack[index]=needle); printf(($""""g""" "b("FOUND at","near")" index "dl$, needle, found, index)) OD; test search(iterative binary search, test cases); test search(recursive binary search, test cases)
)</lang> Output:
"A" near index 1 "Master" FOUND at index 4 "Monk" near index 8 "ZZZ" near index 8
AutoHotkey
<lang AutoHotkey>array := "1,2,4,6,8,9" StringSplit, A, array, `, ; creates associative array MsgBox % x := BinarySearch(A, 4, 1, A0) ; Recursive MsgBox % A%x% MsgBox % x := BinarySearchI(A, A0, 4) ; Iterative MsgBox % A%x%
BinarySearch(A, value, low, high) { ; A0 contains length of array
If (high < low) ; A1, A2, A3...An are array elements Return not_found mid := Floor((low + high) / 2) If (A%mid% > value) ; A%mid% is automatically global since no such locals are present Return BinarySearch(A, value, low, mid - 1) Else If (A%mid% < value) Return BinarySearch(A, value, mid + 1, high) Else Return mid
}
BinarySearchI(A, lengthA, value) {
low := 0 high := lengthA - 1 While (low <= high) { mid := Floor((low + high) / 2) ; round to lower integer If (A%mid% > value) high := mid - 1 Else If (A%mid% < value) low := mid + 1 Else Return mid } Return not_found
}</lang>
BASIC
Recursive
<lang freebasic> FUNCTION binary_search ( array() AS Integer, value AS Integer, lo AS Integer, hi AS Integer) AS Integer
DIM middle AS Integer IF hi < lo THEN binary_search = 0 ELSE middle = (hi + lo) / 2 SELECT CASE value CASE IS < array(middle)
binary_search = binary_search(array(), value, lo, middle-1)
CASE IS > array(middle)
binary_search = binary_search(array(), value, middle+1, hi)
CASE ELSE
binary_search = middle
END SELECT END IF
END FUNCTION </lang>
Iterative
<lang freebasic> FUNCTION binary_search ( array() AS Integer, value AS Integer, lo AS Integer, hi AS Integer) AS Integer
DIM middle AS Integer WHILE lo <= hi middle = (hi + lo) / 2 SELECT CASE value CASE IS < array(middle)
hi = middle - 1
CASE IS > array(middle)
lo = middle + 1
CASE ELSE
binary_search = middle EXIT FUNCTION
END SELECT WEND binary_search = 0
END FUNCTION </lang>
Testing the function
The following program can be used to test both recursive and iterative version. <lang freebasic> SUB search (array() AS Integer, value AS Integer)
DIM idx AS Integer
idx = binary_search(array(), value, LBOUND(array), UBOUND(array)) PRINT "Value "; value; IF idx < 1 THEN PRINT " not found" ELSE PRINT " found at index "; idx END IF
END SUB
DIM test(1 TO 10) AS Integer DIM i AS Integer
DATA 2, 3, 5, 6, 8, 10, 11, 15, 19, 20 FOR i = 1 TO 10 ' Fill the test array
READ test(i)
NEXT i
search test(), 4 search test(), 8 search test(), 20 </lang>
Output:
Value 4 not found Value 8 found at index 5 Value 20 found at index 10
Brat
<lang brat>binary_search = { search_array, value, low, high |
true? high < low
{ null } { mid = ((low + high) / 2).to_i true? search_array[mid] > value { binary_search search_array, value, low, mid - 1 } { true? search_array[mid] < value { binary_search search_array, value, mid + 1, high } { mid } } } }
- Populate array
numbers = [] 1000.times { i | numbers << random i }
- Sort the array
numbers.sort!
- Find a number
x = random 1000
p "Looking for #{x}"
index = binary_search numbers, x, 0, numbers.length
null? index { p "Not found" } { p "Found at index: #{index}" }</lang>
C
Iterative <lang c>/* http://www.solipsys.co.uk/b_search/spec.htm */ typedef int Object;
int cmpObject(Object* pa, Object *pb) {
Object a = *pa; Object b = *pb; if (a < b) return -1; if (a == b) return 0; if (a > b) return 1; assert(0);
}
int bsearch(Object Array[], int n, Object *KeyPtr, int (*cmp)(Object *, Object *),
int NotFound)
{
unsigned left = 1, right = n; /* `unsigned' to avoid overflow in `(left + right)/2' */
if ( ! (Array && n > 0 && KeyPtr && cmp)) return NotFound; /* invalid input or empty array */
while (left < right) { /* invariant: a[left] <= *KeyPtr <= a[right] or *KeyPtr not in Array */ unsigned m = (left + right) / 2; /*NOTE: *intentionally* truncate for odd sum */ if (cmp(Array + m, KeyPtr) < 0) left = m + 1; /* a[m] < *KeyPtr <= a[right] or *KeyPtr not in Array */ else /* assert(right != m) or infinite loop possible */ right = m; /* a[left] <= *KeyPtr <= a[m] or *KeyPtr not in Array */ } /* assert(left == right) */ return (cmp(Array + right, KeyPtr) == 0) ? right : NotFound;
}</lang>
Example: <lang c>#define DUMMY -1 /* dummy element of array (to adjust indexing from 1..n) */
int main(void) {
Object a[] = {DUMMY, 0, 1, 1, 2, 5}; /* allowed indices from 1 to n including */ int n = sizeof(a)/sizeof(*a) - 1; const int NotFound = -1;
/* key not in Array */ Object key = 4; assert(NotFound == bsearch(a, n, &key, cmpObject, NotFound)); key = DUMMY; assert(NotFound == bsearch(a, n, &key, cmpObject, NotFound)); key = 7; assert(NotFound == bsearch(a, n, &key, cmpObject, NotFound));
/* all possible `n' and `k' for `a' array */ int k; key = 10; /* not in `a` array */ for (n = 0; n <= sizeof(a)/sizeof(*a) - 1; ++n) for (k = n; k>=1; --k) { int index = bsearch(a, n, &a[k], cmpObject, NotFound); assert(index == k || (k==3 && index == 2) || n == 0); /* for equal `1's */ assert(NotFound == bsearch(a, n, &key, cmpObject, NotFound)); } n = sizeof(a)/sizeof(*a) - 1;
/* NULL array */ assert(NotFound == bsearch(NULL, n, &key, cmpObject, NotFound)); /* NULL &key */ assert(NotFound == bsearch(a, n, NULL, cmpObject, NotFound)); /* NULL cmpObject */ assert(1 == bsearch(a, n, &a[1], cmpObject, NotFound)); assert(NotFound == bsearch(a, n, &a[1], NULL, NotFound));
printf("OK\n"); return 0;
}</lang>
Library <lang c>#include <stdlib.h> /* for bsearch */
- include <stdio.h>
int intcmp(const void *a, const void *b) {
/* this is only correct if it doesn't overflow */ return *(const int *)a - *(const int *)b;
}
int main() {
int nums[5] = {2, 3, 5, 6, 8}; int desired = 6; int *ptr = bsearch(&desired, nums, 5, sizeof(int), intcmp); if (ptr == NULL) printf("not found\n"); else printf("index = %d\n", ptr - nums);
return 0;
}</lang>
C++
Recursive <lang cpp>template <class T> int binsearch(const T array[], int len, T what) {
if (len == 0) return -1; int mid = len / 2; if (array[mid] == what) return mid; if (array[mid] < what) { int result = binsearch(array+mid+1, len-(mid+1), what); if (result == -1) return -1; else return result + mid+1; } if (array[mid] > what) return binsearch(array, mid, what);
}
- include <iostream>
int main() {
int array[] = {2, 3, 5, 6, 8}; int result1 = binsearch(array, sizeof(array)/sizeof(int), 4), result2 = binsearch(array, sizeof(array)/sizeof(int), 8); if (result1 == -1) std::cout << "4 not found!" << std::endl; else std::cout << "4 found at " << result1 << std::endl; if (result2 == -1) std::cout << "8 not found!" << std::endl; else std::cout << "8 found at " << result2 << std::endl;
return 0;
}</lang>
Iterative <lang cpp>template <class T> int binSearch(const T arr[], int len, T what) {
int low = 0; int high = len - 1; while (low <= high) { int mid = (low + high) / 2; if (arr[mid] > what) high = mid - 1; else if (arr[mid] < what) low = mid + 1; else return mid; } return -1; // indicate not found
}</lang>
Library C++'s Standard Template Library has four functions for binary search, depending on what information you want to get. They all need<lang cpp>#include <algorithm></lang>
The lower_bound()
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.
<lang cpp>int *ptr = std::lower_bound(array, array+len, what); // a custom comparator can be given as fourth arg</lang>
The upper_bound()
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.
<lang cpp>int *ptr = std::upper_bound(array, array+len, what); // a custom comparator can be given as fourth arg</lang>
The equal_range()
function returns a pair of the results of lower_bound()
and upper_bound()
.
<lang cpp>std::pair<int *, int *> bounds = std::equal_range(array, array+len, what); // a custom comparator can be given as fourth arg</lang>
Note that the difference between the bounds is the number of elements equal to the element you want.
The binary_search()
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.
<lang cpp>bool found = std::binary_search(array, array+len, what); // a custom comparator can be given as fourth arg</lang>
C#
<lang csharp>using System;
namespace BinarySearch {
class Program { static void Main(string[] args) {
int[] a = new int[] { 2, 4, 6, 8, 9 }; Console.WriteLine(BinarySearchIterative(a, 9)); Console.WriteLine(BinarySearchRecursive(a, 9, 0, a.Length)); }
private static int BinarySearchIterative(int[] a, int val){ int low = 0; int high = a.Length; while (low <= high) { int mid = (low + high) / 2; if (a[mid] > val) high = mid-1; else if (a[mid] < val) low = mid+1; else return mid; } return -1; }
private static int BinarySearchRecursive(int[] a, int val, int low, int high) { if (high < low) return -1; int mid = (low + high) / 2; if (a[mid] > val) return BinarySearchRecursive(a, val, low, mid - 1); else if (a[mid] < val) return BinarySearchRecursive(a, val, mid + 1, high); else return mid; } }
}</lang>
Clojure
Recursive <lang clojure>(defn bsearch
([coll t] (bsearch coll 0 (dec (count coll)) t)) ([coll l u t] (if (> l u) -1 (let [m (quot (+ l u) 2) mth (nth coll m)] (cond ; the middle element is greater than t ; so search the lower half (> mth t) (recur coll l (dec m) t) ; the middle element is less than t ; so search the upper half (< mth t) (recur coll (inc m) u t) ; we've found our target ; so return its index (= mth t) m)))))</lang>
Common Lisp
Iterative <lang lisp>(defun binary-search (value array)
(let ((low 0) (high (1- (length array)))) (do () ((< high low) nil) (let ((middle (floor (/ (+ low high) 2)))) (cond ((> (aref array middle) value) (setf high (1- middle))) ((< (aref array middle) value) (setf low (1+ middle))) (t (return middle)))))))</lang>
Recursive <lang lisp>(defun binary-search (value array &optional (low 0) (high (1- (length array))))
(if (< high low) nil (let ((middle (floor (/ (+ low high) 2)))) (cond ((> (aref array middle) value) (binary-search value array low (1- middle))) ((< (aref array middle) value) (binary-search value array (1+ middle) high)) (t middle)))))</lang>
D
Recursive
<lang d>bool binarySearch(T)(T[] input, T value) {
if (input.empty) return false; auto i = input.length / 2; auto mid = input[i]; if (mid > value) return binarySearch(input[0 .. i], value); if (mid < value) return binarySearch(input[i + 1 .. $], value); return true;
}</lang>
Iterative <lang d>bool binarySearch(T)(T[] input, T value) {
while (!input.empty) { auto i = input.length / 2; auto mid = input[i]; if (mid > value) input = input[0 .. i]; else if (mid < value) input = input[i + 1 .. $]; else return true; } return false;
}</lang>
E
<lang e>/** Returns null if the value is not found. */ def binarySearch(collection, value) {
var low := 0 var high := collection.size() - 1 while (low <= high) { def mid := (low + high) // 2 def comparison := value.op__cmp(collection[mid]) if (comparison.belowZero()) { high := mid - 1 } \ else if (comparison.aboveZero()) { low := mid + 1 } \ else if (comparison.isZero()) { return mid } \ else { throw("You expect me to binary search with a partial order?") } } return null
}</lang>
F#
Generic recursive version, using #light syntax: <lang fsharp>let rec binarySearch (myArray:array<IComparable>, low:int, high:int, value:IComparable) =
if (high < low) then null else let mid = (low + high) / 2
if (myArray.[mid] > value) then binarySearch (myArray, low, mid-1, value) else if (myArray.[mid] < value) then binarySearch (myArray, mid+1, high, value) else myArray.[mid]
</lang>
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. <lang factor>USING: binary-search kernel math.order ;
- binary-search ( seq elt -- index/f )
[ [ <=> ] curry search ] keep = [ drop f ] unless ;</lang>
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. <lang forth>defer (compare) ' - is (compare) \ default to numbers
- cstr-compare ( cstr1 cstr2 -- <=> ) \ counted strings
swap count rot count compare ;
- mid ( u l -- mid ) tuck - 2/ -cell and + ;
- bsearch ( item upper lower -- where found? )
rot >r begin 2dup > while 2dup mid dup @ r@ (compare) dup while 0< if nip cell+ ( upper mid+1 ) else rot drop swap ( mid lower ) then repeat drop nip nip true else max ( insertion-point ) false then r> drop ;
create test 2 , 4 , 6 , 9 , 11 , 99 ,
- probe ( n -- ) test 5 cells bounds bsearch . @ . cr ;
1 probe \ 0 2 2 probe \ -1 2 3 probe \ 0 4 10 probe \ 0 11 11 probe \ -1 11 12 probe \ 0 99</lang>
Fortran
Recursive In ISO Fortran 90 or later use a RECURSIVE function and ARRAY SECTION argument: <lang fortran>recursive function binarySearch_R (a, value) result (bsresult)
real, intent(in) :: a(:), value integer :: bsresult, mid mid = size(a)/2 + 1 if (size(a) == 0) then bsresult = 0 ! not found else if (a(mid) > value) then bsresult= binarySearch_R(a(:mid-1), value) else if (a(mid) < value) then bsresult = binarySearch_R(a(mid+1:), value) if (bsresult /= 0) then bsresult = mid + bsresult end if else bsresult = mid ! SUCCESS!! end if
end function binarySearch_R</lang>
Iterative In ISO Fortran 90 or later use an ARRAY SECTION POINTER: <lang fortran>function binarySearch_I (a, value)
integer :: binarySearch_I real, intent(in), target :: a(:) real, intent(in) :: value real, pointer :: p(:) integer :: mid, offset p => a binarySearch_I = 0 offset = 0 do while (size(p) > 0) mid = size(p)/2 + 1 if (p(mid) > value) then p => p(:mid-1) else if (p(mid) < value) then offset = offset + mid p => p(mid+1:) else binarySearch_I = offset + mid ! SUCCESS!! return end if end do
end function binarySearch_I</lang>
GAP
<lang gap>Find := function(v, x)
local low, high, mid; low := 1; high := Length(v); while low <= high do mid := QuoInt(low + high, 2); if v[mid] > x then high := mid - 1; elif v[mid] < x then low := mid + 1; else return mid; fi; od; return fail;
end;
u := [1..10]*7;
- [ 7, 14, 21, 28, 35, 42, 49, 56, 63, 70 ]
Find(u, 34);
- fail
Find(u, 35);
- 5</lang>
Go
Recursive: <lang go>func binarySearch(a []float64, value float64, low int, high int) int {
if high < low { return -1 } mid := (low + high) / 2 if a[mid] > value { return binarySearch(a, value, low, mid-1) } else if a[mid] < value { return binarySearch(a, value, mid+1, high) } return mid
}</lang>
Iterative: <lang go>func binarySearch(a []float64, value float64) int {
low := 0 high := len(a) - 1 for low <= high { mid := (low + high) / 2 if a[mid] > value { high = mid - 1 } else if a[mid] < value { low = mid + 1 } else { return mid } } return -1
}</lang>
Library: <lang go>import "sort"
//...
sort.SearchInts([]int{0,1,4,5,6,7,8,9}, 6) // evaluates to 4</lang>
There are also functions sort.SearchFloat64s()
, sort.SearchStrings()
, and a very general sort.Search()
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).
Haskell
The algorithm itself, parametrized by an "interrogation" predicate p in the spirit of the explanation above:
<lang haskell>binarySearch :: Integral a => (a -> Ordering) -> (a, a) -> Maybe a binarySearch p (low,high)
| high < low = Nothing | otherwise = let mid = (low + high) `div` 2 in case p mid of LT -> binarySearch p (low, mid-1) GT -> binarySearch p (mid+1, high) EQ -> Just mid</lang>
Application to an array:
<lang haskell>import Data.Array
binarySearchArray :: (Ix i, Integral i, Ord e) => Array i e -> e -> Maybe i binarySearchArray a x = binarySearch p (bounds a) where
p m = x `compare` (a ! m)</lang>
The algorithm uses tail recursion, so the iterative and the recursive approach are identical in Haskell (the compiler will convert recursive calls into jumps).
HicEst
<lang hicest>REAL :: n=10, array(n)
array = NINT( RAN(n) ) SORT(Vector=array, Sorted=array) x = NINT( RAN(n) )
idx = binarySearch( array, x ) WRITE(ClipBoard) x, "has position ", idx, "in ", array END
FUNCTION binarySearch(A, value)
REAL :: A(1), value
low = 1 high = LEN(A) DO i = 1, high IF( low > high) THEN binarySearch = 0 RETURN ELSE mid = INT( (low + high) / 2 ) IF( A(mid) > value) THEN high = mid - 1 ELSEIF( A(mid) < value ) THEN low = mid + 1 ELSE binarySearch = mid RETURN ENDIF ENDIF ENDDO END</lang>
<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</lang>
Icon and Unicon
Only a recursive solution is shown here. <lang icon>procedure binsearch(A, target)
if *A = 0 then fail mid := *A/2 + 1 if target > A[mid] then { return mid + binsearch(A[(mid+1):0], target) } else if target < A[mid] then { return binsearch(A[1+:(mid-1)], target) } return mid
end</lang> A program to test this is: <lang icon>procedure main(args)
target := integer(!args) | 3 every put(A := [], 1 to 18 by 2)
outList("Searching", A) write(target," is ",("at "||binsearch(A, target)) | "not found")
end
procedure outList(prefix, A)
writes(prefix,": ") every writes(!A," ") write()
end</lang> with some sample runs:
->bins 0 Searching: 1 3 5 7 9 11 13 15 17 0 is not found ->bins 1 Searching: 1 3 5 7 9 11 13 15 17 1 is at 1 ->bins 2 Searching: 1 3 5 7 9 11 13 15 17 2 is not found ->bins 3 Searching: 1 3 5 7 9 11 13 15 17 3 is at 2 ->bins 16 Searching: 1 3 5 7 9 11 13 15 17 16 is not found ->bins 17 Searching: 1 3 5 7 9 11 13 15 17 17 is at 9 ->bins 7 Searching: 1 3 5 7 9 11 13 15 17 7 is at 4 ->bins 9 Searching: 1 3 5 7 9 11 13 15 17 9 is at 5 ->bins 10 Searching: 1 3 5 7 9 11 13 15 17 10 is not found ->
J
J already includes a binary search primitive (I.
). 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:
<lang j>bs=. i. 'Not Found'"_^:(-.@-:) I.</lang>
Examples:
<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
Not Found</lang>
Direct tacit iterative and recursive versions to compare to other implementations follow:
Iterative <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)
boxes=. ; , a: $~ 3: NB. Appending 3 (empty) boxes to the inputs LowHigh=. (0 ; # o (X f)) (L,H)} ] NB. Setting the low and high bounds midpoint=. < o (<. o (2 %~ L f + H f)) M} ] NB. Updating the midpoint case=. >: o * o (Y f - M f { X f) NB. Less=0, equal=1, or greater=2
squeeze=. (< o (_1 + M f) H} ])`(< o _: L} ])`(< o (1 + M f) L} ])@.case return=. (M f) o ((<@:('Not Found'"_) M} ]) ^: (_ ~: L f))
bs=. return o (squeeze o midpoint ^: (L f <: H f) ^:_) o LowHigh o boxes</lang> Recursive <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)
boxes=. a: ,~ ; NB. Appending 1 (empty) box to the inputs midpoint=. < o (<. o (2 %~ L f + H f)) M} ] NB. Updating the midpoint case=. >: o * o (Y f - M f { X f) NB. Less=0, equal=1, or greater=2
recur=. (X f bs Y f ; L f ; (_1 + M f))`(M f)`(X f bs Y f ; (1 + M f) ; H f)@.case
bs=. (recur o midpoint`('Not Found'"_) @. (H f < L f) o boxes) :: ([ bs ] ; 0 ; (<: o # o [))</lang>
Java
Iterative <lang java>... //check will be the number we are looking for //nums will be the array we are searching through public static int binarySearch(int[] nums, int check){
int hi = nums.length - 1; int lo = 0; while(hi >= lo){ guess = lo + ((hi - lo) / 2); if(nums[guess] > check){ hi = guess - 1; }else if(nums[guess] < check){ lo = guess + 1; }else{ return guess; } } return -1;
}
public static void main(String[] args){
int[] searchMe; int someNumber; ... int index = binarySearch(searchMe, someNumber); System.out.println(someNumber + ((index == -1) ? " is not in the array" : (" is at index " + index))); ...
}</lang>
Recursive <lang java>public static void main(String[] args){
int[] searchMe; int someNumber; ... int index = binarySearch(searchMe, someNumber, 0, searchMe.length); System.out.println(someNumber + ((index == -1) ? " is not in the array" : (" is at index " + index))); ...
}
public static int binarySearch(int[] nums, int check, int lo, int hi){
if(hi < lo){ return -1; //impossible index for "not found" } int guess = (hi + lo) / 2; if(nums[guess] > check){ return binarySearch(nums, check, lo, guess - 1); }else if(nums[guess]<check){ return binarySearch(nums, check, guess + 1, hi); } return guess;
}</lang>
Library
When the key is not found, the following functions return ~insertionPoint
(the bitwise complement of the index where the key would be inserted, which is guaranteed to be a negative number).
For arrays: <lang java>import java.util.Arrays;
int index = Arrays.binarySearch(array, thing); int index = Arrays.binarySearch(array, startIndex, endIndex, thing);
// for objects, also optionally accepts an additional comparator argument: int index = Arrays.binarySearch(array, thing, comparator); int index = Arrays.binarySearch(array, startIndex, endIndex, thing, comparator);</lang>
For Lists: <lang java>import java.util.Collections;
int index = Collections.binarySearch(list, thing); int index = Collections.binarySearch(list, thing, comparator);</lang>
JavaScript
A straightforward implementation of the pseudocode
Recursive <lang javascript>function binary_search_recursive(a, value, lo, hi) {
if (hi < lo) return null; var mid = Math.floor((lo+hi)/2); if (a[mid] > value) return binary_search_recursive(a, value, lo, mid-1); else if (a[mid] < value) return binary_search_recursive(a, value, mid+1, hi); else return mid;
}</lang>
Iterative <lang javascript>function binary_search_iterative(a, value) {
lo = 0; hi = a.length - 1; while (lo <= hi) { var mid = Math.floor((lo+hi)/2); if (a[mid] > value) hi = mid - 1; else if (a[mid] < value) lo = mid + 1; else return mid; } return null;
}</lang>
Logo
<lang logo>to bsearch :value :a :lower :upper
if :upper < :lower [output []] localmake "mid int (:lower + :upper) / 2 if item :mid :a > :value [output bsearch :value :a :lower :mid-1] if item :mid :a < :value [output bsearch :value :a :mid+1 :upper] output :mid
end</lang>
Lua
Iterative <lang lua>function binarySearch (list,value)
local low = 0 local high = #list local mid = 0 while low <= high do mid = math.floor((low+high)/2) if list[mid] > value then high = mid - 1 else if list[mid] < value then low = mid + 1 else return mid end end end return false
end</lang> Recursive <lang lua>function binarySearch (list, value)
local function search(low, high) local mid = math.floor((low+high)/2) if list[mid] > value then return search(low,mid-1) end if list[mid] < value then return search(mid+1,high) end return mid end return search(0,#list)
end</lang>
M4
<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)</lang>
Output:
3 -1
Mathematica
Recursive <lang Mathematica>BinarySearchRecursive[x_List, val_, lo_, hi_] :=
Module[{mid = lo + Round@((hi - lo)/2)}, If[hi < lo, Return[-1]]; Return[ Which[xmid > val, BinarySearchRecursive[x, val, lo, mid - 1], xmid < val, BinarySearchRecursive[x, val, mid + 1, hi], True, mid] ]; ]</lang>
Iterative
<lang Mathematica>BinarySearch[x_List, val_] := Module[{lo = 1, hi = Length@x, mid},
While[lo <= hi, mid = lo + Round@((hi - lo)/2); Which[xmid > val, hi = mid - 1, xmid < val, lo = mid + 1, True, Return[mid] ]; ]; Return[-1]; ]</lang>
MATLAB
Recursive <lang MATLAB>function mid = binarySearchRec(list,value,low,high)
if( high < low ) mid = []; return end mid = floor((low + high)/2); if( list(mid) > value ) mid = binarySearchRec(list,value,low,mid-1); return elseif( list(mid) < value ) mid = binarySearchRec(list,value,mid+1,high); return else return end
end</lang>
Sample Usage: <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 =
7</lang>
Iterative <lang MATLAB>function mid = binarySearchIter(list,value)
low = 0; high = numel(list) - 1; while( low <= high ) mid = floor((low + high)/2); if( list(mid) > value ) high = mid - 1; elseif( list(mid) < value ) low = mid + 1; else return end end mid = [];
end</lang>
Sample Usage: <lang MATLAB>>> binarySearchIter([1 2 3 4 5 6 6.5 7 8 9 11 18],6.5)
ans =
7</lang>
MAXScript
Iterative <lang maxscript>fn binarySearchIterative arr value = (
lower = 1 upper = arr.count while lower <= upper do ( mid = (lower + upper) / 2 if arr[mid] > value then ( upper = mid - 1 ) else if arr[mid] < value then ( lower = mid + 1 ) else ( return mid ) ) -1
)
arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10) result = binarySearchIterative arr 6</lang>
Recursive <lang maxscript>fn binarySearchRecursive arr value lower upper = (
if lower == upper then ( if arr[lower] == value then ( return lower ) else ( return -1 ) ) mid = (lower + upper) / 2 if arr[mid] > value then ( return binarySearchRecursive arr value lower (mid-1) ) else if arr[mid] < value then ( return binarySearchRecursive arr value (mid+1) upper ) else ( return mid )
)
arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10) result = binarySearchRecursive arr 6 1 arr.count</lang>
Niue
Library <lang ocaml>1 2 3 4 5 3 bsearch . ( => 2 ) 5 bsearch . ( => 0 ) 'sam 'tom 'kenny ( must be sorted before calling bsearch ) sort .s ( => kenny sam tom ) 'sam bsearch . ( => 1 ) 'tom bsearch . ( => 0 ) 'kenny bsearch . ( => 2 ) 'tony bsearch . ( => -1) </lang>
Objeck
Iterative <lang objeck> use Structure;
bundle Default {
class BinarySearch { function : Main(args : String[]) ~ Nil { values := [-1, 3, 8, 13, 22]; DoBinarySearch(values, 13)->PrintLine(); DoBinarySearch(values, 7)->PrintLine(); } function : native : DoBinarySearch(values : Int[], value : Int) ~ Int { low := 0; high := values->Size() - 1;
while(low <= high) { mid := (low + high) / 2; if(values[mid] > value) { high := mid - 1; } else if(values[mid] < value) { low := mid + 1; } else { return mid; }; };
return -1; } }
} </lang>
Objective-C
Iterative <lang objc>#import <Foundation/Foundation.h>
@interface NSArray (BinarySearch) // Requires all elements of this array to implement a -compare: method which // returns a NSComparisonResult for comparison. // Returns NSNotFound when not found - (NSInteger) binarySearch:(id)key; @end
@implementation NSArray (BinarySearch) - (NSInteger) binarySearch:(id)key {
NSInteger lo = 0; NSInteger hi = [self count] - 1; while (lo <= hi) { NSInteger mid = lo + (hi - lo) / 2; id midVal = [self objectAtIndex:mid]; switch ([midVal compare:key]) { case NSOrderedAscending: lo = mid + 1; break; case NSOrderedDescending: hi = mid - 1; break; case NSOrderedSame: return mid; } } return NSNotFound;
} @end
int main() {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
NSArray *a = [NSArray arrayWithObjects:
[NSNumber numberWithInt: 1], [NSNumber numberWithInt: 3], [NSNumber numberWithInt: 4], [NSNumber numberWithInt: 5], [NSNumber numberWithInt: 6], [NSNumber numberWithInt: 7], [NSNumber numberWithInt: 8], [NSNumber numberWithInt: 9], [NSNumber numberWithInt: 10], nil];
NSLog(@"6 is at position %d", [a binarySearch:[NSNumber numberWithInt: 6]]); // prints 4
[pool drain]; return 0;
}</lang>
Recursive <lang objc>#import <Foundation/Foundation.h>
@interface NSArray (BinarySearchRecursive) // Requires all elements of this array to implement a -compare: method which // returns a NSComparisonResult for comparison. // Returns NSNotFound when not found - (NSInteger) binarySearch:(id)key inRange:(NSRange)range; @end
@implementation NSArray (BinarySearchRecursive) - (NSInteger) binarySearch:(id)key inRange:(NSRange)range {
if (range.length == 0) return NSNotFound; NSInteger mid = range.location + range.length / 2; id midVal = [self objectAtIndex:mid]; switch ([midVal compare:key]) { case NSOrderedAscending: return [self binarySearch:key inRange:NSMakeRange(mid + 1, NSMaxRange(range) - (mid + 1))]; case NSOrderedDescending: return [self binarySearch:key inRange:NSMakeRange(range.location, mid - range.location)]; default: return mid; }
} @end
int main() {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
NSArray *a = [NSArray arrayWithObjects:
[NSNumber numberWithInt: 1], [NSNumber numberWithInt: 3], [NSNumber numberWithInt: 4], [NSNumber numberWithInt: 5], [NSNumber numberWithInt: 6], [NSNumber numberWithInt: 7], [NSNumber numberWithInt: 8], [NSNumber numberWithInt: 9], [NSNumber numberWithInt: 10], nil];
NSLog(@"6 is at position %d", [a binarySearch:[NSNumber numberWithInt: 6] inRange:NSMakeRange(0, [a count])]); // prints 4
[pool drain]; return 0;
}</lang>
Library
<lang objc>#import <Foundation/Foundation.h>
int main() {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
NSArray *a = [NSArray arrayWithObjects:
[NSNumber numberWithInt: 1], [NSNumber numberWithInt: 3], [NSNumber numberWithInt: 4], [NSNumber numberWithInt: 5], [NSNumber numberWithInt: 6], [NSNumber numberWithInt: 7], [NSNumber numberWithInt: 8], [NSNumber numberWithInt: 9], [NSNumber numberWithInt: 10], nil];
NSLog(@"6 is at position %u", [a indexOfObject:[NSNumber numberWithInt: 6] inSortedRange:NSMakeRange(0, [a count]) options:NSBinarySearchingFirstEqual usingComparator:^(id x, id y){ return [x compare: y]; }]); // prints 4
[pool drain]; return 0;
}</lang>
Using Core Foundation (part of Cocoa, all versions): <lang objc>#import <Foundation/Foundation.h>
CFComparisonResult myComparator(const void *x, const void *y, void *context) {
return [(id)x compare:(id)y];
}
int main() {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
NSArray *a = [NSArray arrayWithObjects:
[NSNumber numberWithInt: 1], [NSNumber numberWithInt: 3], [NSNumber numberWithInt: 4], [NSNumber numberWithInt: 5], [NSNumber numberWithInt: 6], [NSNumber numberWithInt: 7], [NSNumber numberWithInt: 8], [NSNumber numberWithInt: 9], [NSNumber numberWithInt: 10], nil];
NSLog(@"6 is at position %d", CFArrayBSearchValues((CFArrayRef)a, CFRangeMake(0, [a count]), [NSNumber numberWithInt: 6], myComparator, NULL)); // prints 4
[pool drain]; return 0;
}</lang>
OCaml
Recursive <lang ocaml>let rec binary_search a value low high =
if high = low then if a.(low) = value then low else raise Not_found else let mid = (low + high) / 2 in if a.(mid) > value then binary_search a value low (mid - 1) else if a.(mid) < value then binary_search a value (mid + 1) high else mid</lang>
Output:
# let arr = [|1; 3; 4; 5; 6; 7; 8; 9; 10|];; val arr : int array = [|1; 3; 4; 5; 6; 7; 8; 9; 10|] # binary_search arr 6 0 (Array.length arr - 1);; - : int = 4 # binary_search arr 2 0 (Array.length arr - 1);; Exception: Not_found.
OCaml supports proper tail-recursion; so this is effectively the same as iteration.
Octave
Recursive <lang octave>function i = binsearch_r(array, val, low, high)
if ( high < low ) i = 0; else mid = floor((low + high) / 2); if ( array(mid) > val ) i = binsearch_r(array, val, low, mid-1); elseif ( array(mid) < val ) i = binsearch_r(array, val, mid+1, high); else i = mid; endif endif
endfunction</lang>
Iterative <lang octave>function i = binsearch(array, value)
low = 1; high = numel(array); i = 0; while ( low <= high ) mid = floor((low + high)/2); if (array(mid) > value) high = mid - 1; elseif (array(mid) < value) low = mid + 1; else i = mid; return; endif endwhile
endfunction</lang>
Example of using <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)</lang>
Oz
Recursive <lang oz>declare
fun {BinarySearch Arr Val} fun {Search Low High} if Low > High then nil else Mid = (Low+High) div 2 in if Val < Arr.Mid then {Search Low Mid-1} elseif Val > Arr.Mid then {Search Mid+1 High} else [Mid] end end end in {Search {Array.low Arr} {Array.high Arr}} end
A = {Tuple.toArray unit(2 3 5 6 8)}
in
{System.printInfo "searching 4: "} {Show {BinarySearch A 4}} {System.printInfo "searching 8: "} {Show {BinarySearch A 8}}</lang>
Iterative <lang oz>declare
fun {BinarySearch Arr Val} Low = {NewCell {Array.low Arr}} High = {NewCell {Array.high Arr}} in for while:@Low =< @High return:Return default:nil do Mid = (@Low + @High) div 2 in if Val < Arr.Mid then High := Mid-1 elseif Val > Arr.Mid then Low := Mid+1 else {Return [Mid]} end end end
A = {Tuple.toArray unit(2 3 5 6 8)}
in
{System.printInfo "searching 4: "} {Show {BinarySearch A 4}} {System.printInfo "searching 8: "} {Show {BinarySearch A 8}}</lang>
PARI/GP
Note that, despite the name, setsearch
works on sorted vectors as well as sets.
<lang>setsearch(s)</lang>
Pascal
Iterative <lang pascal>function binary_search(element: real; list: array of real): integer; var
l, m, h: integer;
begin
l := 0; h := High(list) - 1; binary_search := -1; while l <= h do begin m := (l + h) div 2; if list[m] > element then begin h := m - 1; end else if list[m] < element then begin l := m + 1; end else begin binary_search := m; break; end; end;
end;</lang>
Usage: <lang pascal>var
list: array[0 .. 9] of real;
// ... indexof := binary_search(123, list);</lang>
Perl
Iterative <lang perl>sub binary_search {
($array_ref, $value, $left, $right) = @_; while ($left <= $right) { $middle = ($right + $left) / 2; if ($array_ref->[$middle] == $value) { return 1; } if ($value < $array_ref->[$middle]) { $right = $middle - 1; } else { $left = $middle + 1; } } return 0;
}</lang>
Recursive <lang perl>sub binary_search {
($array_ref, $value, $left, $right) = @_; if ($right < $left) { return 0; } $middle = ($right + $left) / 2; if ($array_ref->[$middle] == $value) { return 1; } if ($value < $array_ref->[$middle]) { binary_search($array_ref, $value, $left, $middle - 1); } else { binary_search($array_ref, $value, $middle + 1, $right); }
}</lang>
Perl 6
With either of the below implementations of binary_search
, one could write a function to search any object that does Positional
this way:
<lang perl6>sub search (@a, Num $x --> Int) {
binary_search { $x <=> @a[$^i] }, 0, @a.end
}</lang>
Iterative <lang perl6>sub binary_search (&p, Int $lo is copy, Int $hi is copy --> Int) {
until $lo > $hi { my Int $mid = ($lo + $hi) div 2; given p $mid { when -1 { $hi = $mid - 1; } when 1 { $lo = $mid + 1; } default { return $mid; } } } fail;
}</lang>
Recursive
<lang perl6>sub binary_search (&p, Int $lo, Int $hi --> Int) {
$lo <= $hi or fail; my Int $mid = ($lo + $hi) div 2; given p $mid { when -1 { binary_search &p, $lo, $mid - 1 } when 1 { binary_search &p, $mid + 1, $hi } default { $mid } }
}</lang>
PHP
Iterative <lang php>function binary_search( $array, $secret, $start, $end ) {
do { $guess = (int)($start + ( ( $end - $start ) / 2 ));
if ( $array[$guess] > $secret ) $end = $guess;
if ( $array[$guess] < $secret ) $start = $guess;
if ( $end < $start) return -1;
} while ( $array[$guess] != $secret );
return $guess;
}</lang> Recursive <lang php>function binary_search( $array, $secret, $start, $end ) {
$guess = (int)($start + ( ( $end - $start ) / 2 ));
if ( $end < $start) return -1;
if ( $array[$guess] > $secret ) return (binary_search( $array, $secret, $start, $guess ));
if ( $array[$guess] < $secret ) return (binary_search( $array, $secret, $guess, $end ) );
return $guess;
}</lang>
PicoLisp
Recursive <lang PicoLisp>(de recursiveSearch (Val Lst Len)
(unless (=0 Len) (let (N (inc (/ Len 2)) L (nth Lst N)) (cond ((= Val (car L)) Val) ((> Val (car L)) (recursiveSearch Val (cdr L) (- Len N)) ) (T (recursiveSearch Val Lst (dec N))) ) ) ) )</lang>
Output:
: (recursiveSearch 5 (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9) -> 5 : (recursiveSearch '(a b) (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9) -> (a b) : (recursiveSearch (9) (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9) -> NIL
Iterative <lang PicoLisp>(de iterativeSearch (Val Lst Len)
(use (N L) (loop (T (=0 Len)) (setq N (inc (/ Len 2)) L (nth Lst N) ) (T (= Val (car L)) Val) (if (> Val (car L)) (setq Lst (cdr L) Len (- Len N)) (setq Len (dec N)) ) ) ) )</lang>
Output:
: (iterativeSearch 5 (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9) -> 5 : (iterativeSearch '(a b) (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9) -> (a b) : (iterativeSearch (9) (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9) -> NIL
PL/I
<lang PL/I> /* A binary search of list A for element M */ search: procedure (A, M) returns (fixed binary);
declare (A(*), M) fixed binary; declare (l, r, mid) fixed binary;
l = lbound(a,1)-1; r = hbound(A,1)+1; do while (l+1 < r); mid = (l+r)/2; if A(mid) = M then return (mid); if A(mid) < M then L = mid; else R = mid; end; return (lbound(A,1)-1);
end search; </lang>
Pop11
Iterative
<lang pop11>define BinarySearch(A, value);
lvars low = 1, high = length(A), mid; while low <= high do (low + high) div 2 -> mid; if A(mid) > value then mid - 1 -> high; elseif A(mid) < value then mid + 1 -> low; else return(mid); endif; endwhile; return("not_found");
enddefine;
/* Tests */ lvars A = {2 3 5 6 8};
BinarySearch(A, 4) => BinarySearch(A, 5) => BinarySearch(A, 8) =></lang>
Recursive <lang pop11>define BinarySearch(A, value);
define do_it(low, high); if high < low then return("not_found"); endif; (low + high) div 2 -> mid; if A(mid) > value then do_it(low, mid-1); elseif A(mid) < value then do_it(mid+1, high); else mid; endif; enddefine; do_it(1, length(A));
enddefine;</lang>
PureBasic
Both recursive and iterative procedures are included and called in the code below. <lang PureBasic>#Recursive = 0 ;recursive binary search method
- Iterative = 1 ;iterative binary search method
- NotFound = -1 ;search result if item not found
- Recursive
Procedure R_BinarySearch(Array a(1), value, low, high)
Protected mid If high < low ProcedureReturn #NotFound EndIf mid = (low + high) / 2 If a(mid) > value ProcedureReturn R_BinarySearch(a(), value, low, mid - 1) ElseIf a(mid) < value ProcedureReturn R_BinarySearch(a(), value, mid + 1, high) Else ProcedureReturn mid EndIf
EndProcedure
- Iterative
Procedure I_BinarySearch(Array a(1), value, low, high)
Protected mid While low <= high mid = (low + high) / 2 If a(mid) > value high = mid - 1 ElseIf a(mid) < value low = mid + 1 Else ProcedureReturn mid EndIf Wend
ProcedureReturn #NotFound
EndProcedure
Procedure search (Array a(1), value, method)
Protected idx Select method Case #Iterative idx = I_BinarySearch(a(), value, 0, ArraySize(a())) Default idx = R_BinarySearch(a(), value, 0, ArraySize(a())) EndSelect Print(" Value " + Str(Value)) If idx < 0 PrintN(" not found") Else PrintN(" found at index " + Str(idx)) EndIf
EndProcedure
- NumElements = 9 ;zero based count
Dim test(#NumElements)
DataSection
Data.i 2, 3, 5, 6, 8, 10, 11, 15, 19, 20
EndDataSection
- fill the test array
For i = 0 To #NumElements
Read test(i)
Next
If OpenConsole()
PrintN("Recursive search:") search(test(), 4, #Recursive) search(test(), 8, #Recursive) search(test(), 20, #Recursive)
PrintN("") PrintN("Iterative search:") search(test(), 4, #Iterative) search(test(), 8, #Iterative) search(test(), 20, #Iterative)
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit") Input() CloseConsole()
EndIf</lang> Sample output:
Recursive search: Value 4 not found Value 8 found at index 4 Value 20 found at index 9 Iterative search: Value 4 not found Value 8 found at index 4 Value 20 found at index 9
Python
Iterative <lang python>def binary_search(l, value):
low = 0 high = len(l)-1 while low <= high: mid = (low+high)//2 if l[mid] > value: high = mid-1 elif l[mid] < value: low = mid+1 else: return mid return -1</lang>
Recursive <lang python>def binary_search(l, value, low = 0, high = -1):
if not l: return -1 if(high == -1): high = len(l)-1 if low == high: if l[low] == value: return low else: return -1 mid = (low+high)//2 if l[mid] > value: return binary_search(l, value, low, mid-1) elif l[mid] < value: return binary_search(l, value, mid+1, high) else: return mid</lang>
Library
Python's bisect
module provides binary search functions
<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
- same as above but actually insert the item into the list at the given place:
bisect.insort_left(list, item) bisect.insort_right(list, item) bisect.insort(list, item)</lang>
R
Recursive
<lang R>BinSearch <- function(A, value, low, high) {
if ( high < low ) { return(NULL) } else { mid <- floor((low + high) / 2) if ( A[mid] > value ) BinSearch(A, value, low, mid-1) else if ( A[mid] < value ) BinSearch(A, value, mid+1, high) else mid }
}</lang>
Iterative
<lang R>IterBinSearch <- function(A, value) {
low = 1 high = length(A) i = 0 while ( low <= high ) { mid <- floor((low + high)/2) if ( A[mid] > value ) high <- mid - 1 else if ( A[mid] < value ) low <- mid + 1 else return(mid) } NULL
}</lang>
Example
<lang R>a <- 1:100 IterBinSearch(a, 50) BinSearch(a, 50, 1, length(a)) # output 50 IterBinSearch(a, 101) # outputs NULL</lang>
REXX
recursive version
Incidentally, REXX doesn't care if the values are integers (or even numbers), as long as they're in order. <lang rexx> /*REXX program finds a value in a list using a recursive binary search. */
@=' 11 17 29 37 41 59 67 71 79 97 101 107 127 137 149',
'163 179 191 197 223 227 239 251 269 277 281 307 311 331 347', '367 379 397 419 431 439 457 461 479 487 499 521 541 557 569', '587 599 613 617 631 641 659 673 701 719 727 739 751 757 769', '787 809 821 827 853 857 877 881 907 929 937 967 991 1009' /*a list of strong primes, btw. */
parse arg ? . /*get a number the user specified*/ if ?== then do; say; say '*** error! *** no arg specified.'; say; exit 13; end
low=1
high=words(@) loc=binarySearch(low,high) if loc==-1 then say ? "wasn't found in the list."
else say ? 'is in the list, its index is:' loc
exit
/*─────────────────────────────────────BINARYSEARCH subroutine──────────*/
binarySearch: procedure expose @ ?;parse arg low,high
if high<low then return -1
mid=(low+high)%2
y=word(@,mid)
if ?=y then return mid
if y>? then return binarySearch(low,mid-1)
else return binarySearch(mid+1,high)
</lang>
Output when using the input of:
499.1
499.1 wasn't found in the list.
Output when using the input of:
499
499 is in the list, its index is: 41
iterative version
<lang rexx> /*REXX program finds a value in a list using an interitive 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 443 449 463 467 491 503 509 523', '547 571 577 601 619 643 647 661 677 683 691 709 743 761 773 797', '811 823 829 839 859 863 883 887 911 919 941 953 971 983 1013' /*a list of weak primes, btw. */
parse arg ? . /*get a number the user specified*/ if ?== then do; say; say '*** error! *** no arg specified.'; say; exit 13; end
low=1
high=words(@)
do while low<=high mid=(low+high)%2 y=word(@,mid) if ?=y then do; say ? 'is in the list, its index is:' mid; exit; end if y>? then high=mid-1 else low=mid+1 end
say ? "wasn't found in the list."
</lang>
Output when using the input of:
-314
-314 wasn't found in the list.
Output when using the input of:
619
619 is in the list, its index is: 53
Ruby
Recursive
<lang ruby>class Array
def binary_search(val, low=0, high=(length - 1)) return nil if high < low mid = (low + high) / 2 case when self[mid] > val then binary_search(val, low, mid-1) when self[mid] < val then binary_search(val, mid+1, high) else mid end end
end
def do_a_binary_search(val, ary, method)
i = ary.send(method, val) if i puts "found #{val} at index #{i}: #{ary[i]}" else puts "#{val} not found in array" end
end
ary = [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] do_a_binary_search(45, ary, :binary_search) do_a_binary_search(42, ary, :binary_search)</lang>
Iterative
<lang ruby>class Array
def binary_search_iterative(val) low, high = 0, length - 1 while low <= high mid = (low + high) / 2 case when self[mid] > val then high = mid - 1 when self[mid] < val then low = mid + 1 else return mid end end nil end
end
ary = [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] do_a_binary_search(45, ary, :binary_search_iterative) do_a_binary_search(42, ary, :binary_search_iterative)</lang>
Scala
<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 case mid if a(mid) > v => recurse(low, mid - 1) case mid if a(mid) < v => recurse(mid + 1, high) case mid => Some(mid) } recurse(0, a.size - 1)
}</lang>
Scheme
Recursive <lang scheme>(define (binary-search value vector)
(let helper ((low 0) (high (- (vector-length vector) 1))) (if (< high low) #f (let ((middle (quotient (+ low high) 2))) (cond ((> (vector-ref vector middle) value) (helper low (- middle 1))) ((< (vector-ref vector middle) value) (helper (+ middle 1) high)) (else middle))))))</lang>
Example:
> (binary-search 6 '#(1 3 4 5 6 7 8 9 10)) 4 > (binary-search 2 '#(1 3 4 5 6 7 8 9 10)) #f
Scheme requires proper tail-recursion; so this is effectively the same as iteration.
Seed7
Iterative <lang seed7>const func integer: binarySearchIterative (in array elemType: arr, in elemType: aKey) is func
result var integer: result is 0; local var integer: low is 1; var integer: high is 0; var integer: middle is 0; begin high := length(arr); while result = 0 and low <= high do middle := low + (high - low) div 2; if aKey < arr[middle] then high := pred(middle); elsif aKey > arr[middle] then low := succ(middle); else result := middle; end if; end while; end func;</lang>
Recursive <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; begin if low <= high then result := (low + high) div 2; if aKey < arr[result] then result := binarySearch(arr, aKey, low, pred(result)); # search left elsif aKey > arr[result] then result := binarySearch(arr, aKey, succ(result), high); # search right end if; end if; end func;
const func integer: binarySearchRecursive (in array elemType: arr, in elemType: aKey) is
return binarySearch(arr, aKey, 1, length(arr));</lang>
SPARK
SPARK does not allow recursion, so only the iterative solution is provided. This example shows the use of a loop assertion.
All the code for this task validates with SPARK GPL 2010 and compiles and executes with GPS GPL 2010.
The Binary_Searches package is shown first. Search is a procedure, rather than a function, so that it can return a Found flag and a Position for Item, if found. This is better design than having a Position value that means 'item not found'.
There are two versions of the package provided, although the Ada code of the two versions is identical.
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 the SPARK Proof Process. <lang Ada>package Binary_Searches is
subtype Item_Type is Integer; -- From specs. subtype Index_Type is Integer range 1 .. 100; type Array_Type is array (Index_Type range <>) of Item_Type;
procedure Search (Source : in Array_Type; Item : in Item_Type; Found : out Boolean; Position : out Index_Type); --# derives Found, --# Position from --# Source, --# Item; --# post Found -> Source (Position) = Item; -- If Found is False then Position is undefined.
end Binary_Searches;
package body Binary_Searches is
procedure Search (Source : in Array_Type; Item : in Item_Type; Found : out Boolean; Position : out Index_Type) is Lower : Index_Type; -- Lower bound of Subrange. Upper : Index_Type; -- Upper bound of Subrange. Terminated : Boolean; begin Found := False; -- Default status updated on success.
Lower := Source'First; Upper := Source'Last; Position := (Lower + Upper) / 2; Terminated := False;
while not Terminated loop --# assert Lower >= Source'First --# and Upper <= Source'Last --# and Position in Lower .. Upper --# and not Found; if Item < Source (Position) then if Position = Lower then -- No lower subrange. Terminated := True; else --# check Position > Lower; -- For the two following proofs.
--# check Position - 1 >= Lower; --# check Lower + Position - 1 >= Lower * 2; --# check (Lower + Position - 1) / 2 >= Lower; -- For "Position >= Lower" in loop assertion.
--# check Lower < Position; --# check Lower + Position - 1 <= (Position - 1) * 2; --# check (Lower + Position - 1) / 2 <= (Position - 1); -- For "Position <= Upper" in loop assertion.
-- Switch to lower half subrange. Upper := Position - 1; Position := (Lower + Upper) / 2; end if;
elsif Item > Source (Position) then if Position = Upper then -- No upper subrange. Terminated := True; else --# check Position < Upper; -- For the two following proofs.
--# check Upper >= Position + 1; --# check Position + 1 + Upper >= (Position + 1) * 2; --# check (Position + 1 + Upper) / 2 >= (Position + 1); -- For "Position >= Lower" in loop assertion.
--# check Position + 1 <= Upper; --# check Position + 1 + Upper <= Upper * 2; --# check (Position + 1 + Upper) / 2 <= Upper; -- For "Position <= Upper" in loop assertion.
-- Switch to upper half subrange. Lower := Position + 1; Position := (Lower + Upper) / 2; end if; else Found := True; Terminated := True; end if; end loop; end Search;
end Binary_Searches; </lang> 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 the SPARK Proof Process) to be provided to the Simplifier so that it can prove all the verification conditions. <lang Ada>package Binary_Searches is
subtype Item_Type is Integer; -- From specs. subtype Index_Type is Integer range 1 .. 100; type Array_Type is array (Index_Type range <>) of Item_Type;
-- Ordered_Between is a 'proof function'. It does not have a code -- body, but its meaning is defined by a proof rule: -- -- Ordered_Between (Source, Low_Bound, High_Bound) -- <-> -- for all I in Index_Type range Low_Bound .. High_Bound - 1 => -- (Source(I) < Source(I + 1)) ; -- --# function Ordered_Between (Source : Array_Type; --# Range_From, Range_To : Index_Type) --# return Boolean;
procedure Search (Source : in Array_Type; Item : in Item_Type; Found : out Boolean; Position : out Index_Type); --# derives Found, --# Position from --# Source, --# Item; --# pre Ordered_Between (Source, Source'First, Source'Last); --# post (Found -> (Source (Position) = Item)) --# and (not Found -> --# (for all I in Index_Type range Source'Range --# => (Source(I) /= Item)));
end Binary_Searches;
package body Binary_Searches is
procedure Search (Source : in Array_Type; Item : in Item_Type; Found : out Boolean; Position : out Index_Type) is Lower : Index_Type; -- Lower bound of Subrange. Upper : Index_Type; -- Upper bound of Subrange. Terminated : Boolean; begin Found := False; -- Default status updated on success.
Lower := Source'First; Upper := Source'Last; Position := (Lower + Upper) / 2; Terminated := False;
while not Terminated loop --# assert not Terminated --# and not Found --# and Lower >= Source'First --# and Upper <= Source'Last --# and Position in Lower .. Upper --# and (Lower = Source'First or --# (Lower > Source'First and Source(Lower - 1) < Item)) --# and (Upper = Source'Last or --# (Upper < Source'Last and Source(Upper + 1) > Item)); if Item < Source (Position) then if Position = Lower then -- No lower subrange. Terminated := True; else -- Switch to lower half subrange. Upper := Position - 1; Position := (Lower + Upper) / 2; end if; elsif Item > Source (Position) then if Position = Upper then -- No upper subrange. Terminated := True; else -- Switch to upper half subrange. Lower := Position + 1; Position := (Lower + Upper) / 2; end if; else Found := True; Terminated := True; end if; end loop; end Search;
end Binary_Searches; </lang> The user rules for this version of the package (written in FDL, a language for modelling algorithms).
binary_search_rule(1): (X + Y) div 2 >= X may_be_deduced_from [ X <= Y, X >= 1, Y >= 1] . binary_search_rule(2): (X + Y) div 2 <= Y may_be_deduced_from [ X <= Y, X >= 1, Y >= 1] . binary_search_rule(3): for_all(I_ : integer, First <= I_ and I_ <= Last -> element(S, [I_]) <> X) may_be_deduced_from [ ordered_between(S, First, Last), P >= First, P <= Last, element(S, [P]) > X, P = First or (P > First and element(S, [P - 1]) < X) ] . binary_search_rule(4): for_all(I_ : integer, First <= I_ and I_ <= Last -> element(S, [I_]) <> X) may_be_deduced_from [ ordered_between(S, First, Last), P >= First, P <= Last, element(S, [P]) < X, P = Last or (P < Last and element(S, [P + 1]) > X) ] .
The test program: <lang Ada>with Binary_Searches; with SPARK_IO;
--# inherit Binary_Searches, --# SPARK_IO;
--# main_program; procedure Test_Binary_Search --# global in out SPARK_IO.Outputs; --# derives SPARK_IO.Outputs from *; is
subtype Index_Type5 is Binary_Searches.Index_Type range 1 .. 5; subtype Index_Type7 is Binary_Searches.Index_Type range 1 .. 7; subtype Index_Type9 is Binary_Searches.Index_Type range 91 .. 99; -- Needed to define a constrained Array_Type.
subtype Array_Type5 is Binary_Searches.Array_Type (Index_Type5); subtype Array_Type7 is Binary_Searches.Array_Type (Index_Type7); subtype Array_Type9 is Binary_Searches.Array_Type (Index_Type9); -- Needed to pass an array literal to Run_Search. -- SPARK does not allow an unconstrained type mark for that purpose.
procedure Run_Search (Source : in Binary_Searches.Array_Type; Item : in Binary_Searches.Item_Type) --# global in out SPARK_IO.Outputs; --# derives SPARK_IO.Outputs from *, --# Item, --# Source; is Found : Boolean; Position : Binary_Searches.Index_Type; begin SPARK_IO.Put_String (File => SPARK_IO.Standard_Output, Item => "Searching for ", Stop => 0); SPARK_IO.Put_Integer (File => SPARK_IO.Standard_Output, Item => Item, Width => 3, Base => 10); SPARK_IO.Put_String (File => SPARK_IO.Standard_Output, Item => " in (", Stop => 0); for Source_Index in Binary_Searches.Index_Type range Source'Range loop SPARK_IO.Put_Integer (File => SPARK_IO.Standard_Output, Item => Source (Source_Index), Width => 3, Base => 10); end loop; SPARK_IO.Put_String (File => SPARK_IO.Standard_Output, Item => "): ", Stop => 0); Binary_Searches.Search (Source => Source, -- in Item => Item, -- in Found => Found, -- out Position => Position); -- out if Found then SPARK_IO.Put_String (File => SPARK_IO.Standard_Output, Item => "found as #", Stop => 0); SPARK_IO.Put_Integer (File => SPARK_IO.Standard_Output, Item => Position, Width => 0, -- to stick to the sibling '#' sign. Base => 10); SPARK_IO.Put_Line (File => SPARK_IO.Standard_Output, Item => ".", Stop => 0); else SPARK_IO.Put_Line (File => SPARK_IO.Standard_Output, Item => "not found.", Stop => 0); end if; end Run_Search;
begin
SPARK_IO.New_Line (File => SPARK_IO.Standard_Output, Spacing => 1); Run_Search (Source => Array_Type5'(0, 1, 2, 3, 4), Item => 3); Run_Search (Source => Array_Type5'(2, 4, 6, 8, 10), Item => 3); Run_Search (Source => Array_Type7'(1, 2, 3, 4, 5, 6, 7), Item => 0); Run_Search (Source => Array_Type7'(1, 2, 3, 4, 5, 6, 7), Item => 7); Run_Search (Source => Array_Type9'(1, 2, 3, 4, 5, 6, 7, 8, 9), Item => 10); Run_Search (Source => Array_Type9'(1, 2, 3, 4, 5, 6, 7, 8, 9), Item => 1); Run_Search (Source => Array_Type9'(1, 2, 3, 4, 5, 6, 7, 8, 9), Item => 6);
end Test_Binary_Search; </lang>
Test output (for the last three tests the array is indexed from 91):
Searching for 3 in ( 0 1 2 3 4): found as #4. Searching for 3 in ( 2 4 6 8 10): not found. Searching for 0 in ( 1 2 3 4 5 6 7): not found. Searching for 7 in ( 1 2 3 4 5 6 7): found as #7. Searching for 10 in ( 1 2 3 4 5 6 7 8 9): not found. Searching for 1 in ( 1 2 3 4 5 6 7 8 9): found as #91. Searching for 6 in ( 1 2 3 4 5 6 7 8 9): found as #96.
Tcl
ref: Tcl wiki <lang tcl>proc binSrch {lst x} {
set len [llength $lst] if {$len == 0} { return -1 } else { set pivotIndex [expr {$len / 2}] set pivotValue [lindex $lst $pivotIndex] if {$pivotValue == $x} { return $pivotIndex } elseif {$pivotValue < $x} { set recursive [binSrch [lrange $lst $pivotIndex+1 end] $x] return [expr {$recursive > -1 ? $recursive + $pivotIndex + 1 : -1}] } elseif {$pivotValue > $x} { set recursive [binSrch [lrange $lst 0 $pivotIndex-1] $x] return [expr {$recursive > -1 ? $recursive : -1}] } }
} proc binary_search {lst x} {
if {[set idx [binSrch $lst $x]] == -1} { puts "element $x not found in list" } else { puts "element $x found at index $idx" }
}</lang> Note also that, from Tcl 8.4 onwards, the lsearch command includes the -sorted option to enable binary searching of Tcl lists. <lang tcl>proc binarySearch {lst x} {
set idx [lsearch -sorted -exact $lst $x] if {$idx == -1} { puts "element $x not found in list" } else { puts "element $x found at index $idx" }
}</lang>
UnixPipes
Parallel <lang bash>splitter() {
a=$1; s=$2; l=$3; r=$4; mid=$(expr ${#a[*]} / 2); echo $s ${a[*]:0:$mid} > $l echo $(($mid + $s)) ${a[*]:$mid} > $r
}
bsearch() {
(to=$1; read s arr; a=($arr); test ${#a[*]} -gt 1 && (splitter $a $s >(bsearch $to) >(bsearch $to)) || (test "$a" -eq "$to" && echo $a at $s) )
}
binsearch() {
(read arr; echo "0 $arr" | bsearch $1)
}
echo "1 2 3 4 6 7 8 9" | binsearch 6</lang>
Vedit macro language
Iterative
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.) <lang vedit>// Main program for testing BINARY_SEARCH
- 3 = Get_Num("Value to search: ")
EOF
- 2 = Cur_Line // hi
- 1 = 1 // lo
Call("BINARY_SEARCH") Message("Value ") Num_Type(#3, NOCR) if (Return_Value < 1) {
Message(" not found\n")
} else {
Message(" found at index ") Num_Type(Return_Value)
} return
- BINARY_SEARCH:
while (#1 <= #2) {
#12 = (#1 + #2) / 2 Goto_Line(#12) #11 = Num_Eval() if (#3 == #11) { return(#12) // found } else { if (#3 < #11) { #2 = #12-1 } else { #1 = #12+1 } }
} return(0) // not found</lang>
Visual Basic .NET
Iterative <lang vbnet>Function BinarySearch(ByVal A() As Integer, ByVal value As Integer) As Integer
Dim low As Integer = 0 Dim high As Integer = A.Length - 1 Dim middle As Integer = 0
While low <= high middle = (low + high) / 2 If A(middle) > value Then high = middle - 1 ElseIf A(middle) < value Then low = middle + 1 Else Return middle End If End While
Return Nothing
End Function</lang>
Recursive <lang vbnet>Function BinarySearch(ByVal A() As Integer, ByVal value As Integer, ByVal low As Integer, ByVal high As Integer) As Integer
Dim middle As Integer = 0
If high < low Then Return Nothing End If
middle = (low + high) / 2
If A(middle) > value Then Return BinarySearch(A, value, low, middle - 1) ElseIf A(middle) < value Then Return BinarySearch(A, value, middle + 1, high) Else Return middle End If
End Function</lang>
- Programming Tasks
- Classic CS problems and programs
- Recursion
- Ada
- ALGOL 68
- AutoHotkey
- BASIC
- Brat
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- E
- F Sharp
- Factor
- Forth
- Fortran
- GAP
- Go
- Haskell
- HicEst
- Icon
- Unicon
- J
- Java
- JavaScript
- Logo
- Lua
- M4
- Mathematica
- MATLAB
- MAXScript
- Niue
- Objeck
- Objective-C
- OCaml
- Octave
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- Pop11
- PureBasic
- Python
- R
- REXX
- Ruby
- Scala
- Scheme
- Seed7
- SPARK
- Tcl
- UnixPipes
- Vedit macro language
- Visual Basic .NET