Binary search

From Rosetta Code
Jump to: navigation, search
Task
Binary search
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 search 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 to high = N
  • change high = mid-1 to high = mid
  • (for recursive algorithm) change if (high < low) to if (high <= low)
  • (for iterative algorithm) change while (low <= high) to while (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.

References:

Contents

[edit] ACL2

(defun defarray (name size initial-element)
(cons name
(compress1 name
(cons (list :HEADER
:DIMENSIONS (list size)
:MAXIMUM-LENGTH (1+ size)
:DEFAULT initial-element
:NAME name)
nil))))
 
(defconst *dim* 100000)
 
(defun array-name (array)
(first array))
 
(defun set-at (array i val)
(cons (array-name array)
(aset1 (array-name array)
(cdr array)
i
val)))
 
(defun populate-array-ordered (array n)
(if (zp n)
array
(populate-array-ordered (set-at array
(- *dim* n)
(- *dim* n))
(1- n))))
(include-book "arithmetic-3/top" :dir :system)
 
(defun binary-search-r (needle haystack low high)
(declare (xargs :measure (nfix (1+ (- high low)))))
(let* ((mid (floor (+ low high) 2))
(current (aref1 (array-name haystack)
(cdr haystack)
mid)))
(cond ((not (and (natp low) (natp high))) nil)
((= current needle)
mid)
((zp (1+ (- high low))) nil)
((> current needle)
(binary-search-r needle
haystack
low
(1- mid)))
(t (binary-search-r needle
haystack
(1+ mid)
high)))))
 
(defun binary-search (needle haystack)
(binary-search-r needle haystack 0
(maximum-length (array-name haystack)
(cdr haystack))))
 
(defun test-bsearch (needle)
(binary-search needle
(populate-array-ordered
(defarray 'haystack *dim* 0)
*dim*)))

[edit] 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
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;
Iterative
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;

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

[edit] ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
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)
)

Output:

"A" near index 1
"Master" FOUND at index 4
"Monk" near index 8
"ZZZ" near index 8

[edit] 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
}

[edit] AWK

Works with: Gawk
Works with: Mawk
Works with: Nawk

Recursive

function binary_search(array, value, left, right,       middle) {
if (right < left) return 0
middle = int((right + left) / 2)
if (value == array[middle]) return 1
if (value < array[middle])
return binary_search(array, value, left, middle - 1)
return binary_search(array, value, middle + 1, right)
}

Iterative

function binary_search(array, value, left, right,       middle) {
while (left <= right) {
middle = int((right + left) / 2)
if (value == array[middle]) return 1
if (value < array[middle]) right = middle - 1
else left = middle + 1
}
return 0
}

[edit] BASIC

Recursive

Works with: FreeBASIC
Works with: RapidQ
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

Iterative

Works with: FreeBASIC
Works with: RapidQ
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

Testing the function

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

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

Output:

Value 4 not found
Value 8 found at index 5
Value 20 found at index 10

[edit] BBC BASIC

      DIM array%(9)
array%() = 7, 14, 21, 28, 35, 42, 49, 56, 63, 70
 
secret% = 42
index% = FNwhere(array%(), secret%, 0, DIM(array%(),1))
IF index% >= 0 THEN
PRINT "The value "; secret% " was found at index "; index%
ELSE
PRINT "The value "; secret% " was not found"
ENDIF
END
 
REM Search ordered array A%() for the value S% from index B% to T%
DEF FNwhere(A%(), S%, B%, T%)
LOCAL H%
H% = 2
WHILE H%<(T%-B%) H% *= 2:ENDWHILE
H% /= 2
REPEAT
IF (B%+H%)<=T% IF S%>=A%(B%+H%) B% += H%
H% /= 2
UNTIL H%=0
IF S%=A%(B%) THEN = B% ELSE = -1

[edit] 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.of { random 1000 }
 
#Sort the array
numbers.sort!
 
#Find a number
x = random 1000
 
p "Looking for #{x}"
 
index = binary_search numbers, x, 0, numbers.length - 1
 
null? index
{ p "Not found" }
{ p "Found at index: #{index}" }

[edit] C

Iterative

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

Example:

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

Library

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

[edit] C++

Recursive

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

Iterative

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
}

Library

C++'s Standard Template Library has four functions for binary search, depending on what information you want to get. They all need
#include <algorithm>

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.

int *ptr = std::lower_bound(array, array+len, what); // a custom comparator can be given as fourth arg

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.

int *ptr = std::upper_bound(array, array+len, what); // a custom comparator can be given as fourth arg

The equal_range() function returns a pair of the results of lower_bound() and upper_bound().

std::pair<int *, int *> bounds = std::equal_range(array, array+len, what); // a custom comparator can be given as fourth arg

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.

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

[edit] C#

Recursive

Translation of: Java
using System;
 
namespace ConsoleApplication7
{
class Program
{
public static void Main(string[] args)
{
int[] array;
int needle;
.....
.....
 
int index = binarySearch(array, needle, 0, array.Length);
Console.WriteLine(needle + ((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;
 
}
}
}

Iterative

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

[edit] Chapel

iterative -- almost a direct translation of the pseudocode

proc binsearch(A:[], value) {
var low = A.domain.dim(1).low;
var high = A.domain.dim(1).high;
while (low <= high) {
var mid = (low + high) / 2;
 
if A(mid) > value then
high = mid - 1;
else if A(mid) < value then
low = mid + 1;
else
return mid;
}
return 0;
}
 
writeln(binsearch([3, 4, 6, 9, 11], 9));
Output:
4

[edit] Clojure

Recursive

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

[edit] COBOL

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

        >>SOURCE FREE
IDENTIFICATION DIVISION.
PROGRAM-ID. binary-search.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 nums-area VALUE "01040612184356".
03 nums PIC 9(2)
OCCURS 7 TIMES
ASCENDING KEY nums
INDEXED BY nums-idx.
PROCEDURE DIVISION.
SEARCH ALL nums
WHEN nums (nums-idx) = 4
DISPLAY "Found 4 at index " nums-idx
END-SEARCH
.
END PROGRAM binary-search.

[edit] CoffeeScript

binsearch = (arr, k) ->
low = 0
high = arr.length - 1
while low <= high
mid = Math.floor (low + high) / 2
return mid if arr[mid] == k
if arr[mid] < k
low = mid + 1
else
high = mid - 1
null
 
arr = [1,3,5,7,9,11]
for i in [0..12]
pos = binsearch arr, i
console.log "found #{i} at pos #{pos}" if pos?

output

> coffee binsearch.coffee 
found 1 at pos 0
found 3 at pos 1
found 5 at pos 2
found 7 at pos 3
found 9 at pos 4
found 11 at pos 5

[edit] Common Lisp

Iterative

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

Recursive

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

[edit] D

import std.stdio, std.array, std.range, std.traits;
 
/// Recursive.
bool binarySearch(R, T)(/*in*/ R data, in T x)
pure nothrow if (isRandomAccessRange!R &&
is(Unqual!T == Unqual!(ElementType!R))) {
if (data.empty)
return false;
immutable i = data.length / 2;
immutable mid = data[i];
if (mid > x)
return data[0 .. i].binarySearch(x);
if (mid < x)
return data[i + 1 .. $].binarySearch(x);
return true;
}
 
/// Iterative.
bool binarySearchIt(R, T)(/*in*/ R data, in T x)
pure nothrow if (isRandomAccessRange!R &&
is(Unqual!T == Unqual!(ElementType!R))) {
while (!data.empty) {
immutable i = data.length / 2;
immutable mid = data[i];
if (mid > x)
data = data[0 .. i];
else if (mid < x)
data = data[i + 1 .. $];
else
return true;
}
return false;
}
 
void main() {
/*const*/ auto items = [2, 4, 6, 8, 9].assumeSorted;
foreach (x; [1, 8, 10, 9, 5, 2])
writefln("%2d %5s %5s %5s", x,
items.binarySearch(x),
items.binarySearchIt(x),
// Standard Binary Search:
!items.equalRange(x).empty);
}
Output:
 1 false false false
 8  true  true  true
10 false false false
 9  true  true  true
 5 false false false
 2  true  true  true

[edit] 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
}

[edit] Erlang

%% Task: Binary Search algorithm
%% Author: Abhay Jain
 
-module(searching_algorithm).
-export([start/0]).
 
start() ->
List = [1,2,3],
binary_search(List, 5, 1, length(List)).
 
 
binary_search(List, Value, Low, High) ->
if Low > High ->
io:format("Number ~p not found~n", [Value]),
not_found;
true ->
Mid = (Low + High) div 2,
MidNum = lists:nth(Mid, List),
if MidNum > Value ->
binary_search(List, Value, Low, Mid-1);
MidNum < Value ->
binary_search(List, Value, Mid+1, High);
true ->
io:format("Number ~p found at index ~p", [Value, Mid]),
Mid
end
end.

[edit] Euphoria

[edit] Recursive

function binary_search(sequence s, object val, integer low, integer high)
integer mid, cmp
if high < low then
return 0 -- not found
else
mid = floor( (low + high) / 2 )
cmp = compare(s[mid], val)
if cmp > 0 then
return binary_search(s, val, low, mid-1)
elsif cmp < 0 then
return binary_search(s, val, mid+1, high)
else
return mid
end if
end if
end function

[edit] Iterative

function binary_search(sequence s, object val)
integer low, high, mid, cmp
low = 1
high = length(s)
while low <= high do
mid = floor( (low + high) / 2 )
cmp = compare(s[mid], val)
if cmp > 0 then
high = mid - 1
elsif cmp < 0 then
low = mid + 1
else
return mid
end if
end while
return 0 -- not found
end function

[edit] F#

Generic recursive version, using #light syntax:

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]

[edit] FBSL

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

#APPTYPE CONSOLE
 
DIM va[], sign = {1, -1}, toggle
 
PRINT "Loading ... ";
DIM gtc = GetTickCount()
FOR DIM i = 0 TO 1000000
va[] = sign[toggle] * PI * i
toggle = NOT toggle ' randomize the array
NEXT
PRINT "done in ", GetTickCount() - gtc, " milliseconds"
 
PRINT "Sorting ... ";
gtc = GetTickCount()
QUICKSORT(va) ' quick sort the array
PRINT "done in ", GetTickCount() - gtc, " milliseconds"
 
gtc = GetTickCount()
PRINT 1000000 * PI, " found at index ", BSEARCH(va, 1000000 * PI), _ ' binary search through the array
" in ", GetTickCount() - gtc, " milliseconds"
 
PAUSE
Output:
Loading ... done in 906 milliseconds
Sorting ... done in 547 milliseconds
3141592.65358979 found at index 1000000 in 0 milliseconds

Press any key to continue...

User-defined implementations of the same would be considerably slower. Nonetheless, here they are in order to comply with the task requirements.

Iterative:

#APPTYPE CONSOLE
 
DIM va[]
 
PRINT "Loading ... ";
DIM gtc = GetTickCount()
FOR DIM i = 0 TO 1000000: va[] = i * PI: NEXT
PRINT "done in ", GetTickCount() - gtc, " milliseconds"
 
gtc = GetTickCount()
PRINT 1000000 * PI, " found at index ", BSearchIter(va, 1000000 * PI), _
" in ", GetTickCount() - gtc, " milliseconds"
 
PAUSE
 
FUNCTION BSearchIter(BYVAL array, BYVAL num)
STATIC low = LBOUND(va), high = UBOUND(va)
WHILE low <= high
DIM midp = (high + low) \ 2
IF array[midp] > num THEN
high = midp - 1
ELSEIF array[midp] < num THEN
low = midp + 1
ELSE
RETURN midp
END IF
WEND
RETURN -1
END FUNCTION
Output:
Loading ... done in 391 milliseconds
3141592.65358979 found at index 1000000 in 62 milliseconds

Press any key to continue...

Recursive:

#APPTYPE CONSOLE
 
DIM va[]
 
PRINT "Loading ... ";
DIM gtc = GetTickCount()
FOR DIM i = 0 TO 1000000: va[] = i * PI: NEXT
PRINT "done in ", GetTickCount() - gtc, " milliseconds"
 
gtc = GetTickCount()
PRINT 1000000 * PI, " found at index ", BSearchRec(va, 1000000 * PI, LBOUND(va), UBOUND(va)), _
" in ", GetTickCount() - gtc, " milliseconds"
 
PAUSE
 
FUNCTION BSearchRec(BYVAL array, BYVAL num, BYVAL low, BYVAL high)
IF high < low THEN RETURN -1
DIM midp = (high + low) \ 2
IF array[midp] > num THEN
RETURN BSearchRec(array, num, low, midp - 1)
ELSEIF array[midp] < num THEN
RETURN BSearchRec(array, num, midp + 1, high)
END IF
RETURN midp
END FUNCTION
Output:
Loading ... done in 390 milliseconds
3141592.65358979 found at index 1000000 in 938 milliseconds

Press any key to continue...

[edit] 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.

USING: binary-search kernel math.order ;
 
: binary-search ( seq elt -- index/f )
[ [ <=> ] curry search ] keep = [ drop f ] unless ;

[edit] 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.

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

[edit] Fortran

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

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

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

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

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

[edit] Go

Recursive:

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
}

Iterative:

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
}

Library:

import "sort"
 
//...
 
sort.SearchInts([]int{0,1,4,5,6,7,8,9}, 6) // evaluates to 4

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

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

[edit] Groovy

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

[edit] Recursive Solution

def binSearchR
binSearchR = { a, target, offset=0 ->
def n = a.size()
def m = n.intdiv(2)
a.empty \
? ["insertion point": offset] \
 : a[m] > target \
? binSearchR(a[0..<m], target, offset) \
 : a[m] < target \
? binSearchR(a[(m + 1)..<n], target, offset + m + 1) \
 : [index: offset + m]
}

[edit] Iterative Solution

def binSearchI = { aList, target ->
def a = aList
def offset = 0
while (!a.empty) {
def n = a.size()
def m = n.intdiv(2)
if(a[m] > target) {
a = a[0..<m]
} else if (a[m] < target) {
a = a[(m + 1)..<n]
offset += m + 1
} else {
return [index: offset + m]
}
}
return ["insertion point": offset]
}

Test:

def a = [] as Set
def random = new Random()
while (a.size() < 20) { a << random.nextInt(30) }
def source = a.sort()
source[0..-2].eachWithIndex { si, i -> assert si < source[i+1] }
 
println "${source}"
1.upto(5) {
target = random.nextInt(10) + (it - 2) * 10
print "Trial #${it}. Looking for: ${target}"
def answers = [binSearchR, binSearchI].collect { search ->
search(source, target)
}
assert answers[0] == answers[1]
println """
Answer: ${answers[0]}, : ${source[answers[0].values().iterator().next()]}"""

}

Output:

[1, 2, 5, 8, 9, 10, 11, 14, 15, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 29]
Trial #1. Looking for: -9
    Answer: [insertion point:0], : 1
Trial #2. Looking for: 7
    Answer: [insertion point:3], : 8
Trial #3. Looking for: 18
    Answer: [index:9], : 18
Trial #4. Looking for: 29
    Answer: [index:19], : 29
Trial #5. Looking for: 32
    Answer: [insertion point:20], : null

[edit] Haskell

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

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

Application to an array:

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)

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

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

[edit] Icon and Unicon

Only a recursive solution is shown here.

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

A program to test this is:

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

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

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

bs=. i. 'Not Found'"_^:(-.@-:) I.

Examples:

   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

Direct tacit iterative and recursive versions to compare to other implementations follow:

Iterative

'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

Recursive

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

[edit] Java

Iterative

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

Recursive

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

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:

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

For Lists:

import java.util.Collections;
 
int index = Collections.binarySearch(list, thing);
int index = Collections.binarySearch(list, thing, comparator);

[edit] JavaScript

A straightforward implementation of the pseudocode

Recursive

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

Iterative

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

[edit] Julia

Iterative

function binary_search(l, value)
low = 1
high = length(l)
while low <= high
mid = int((low+high)/2)
if l[mid] > value
high = mid-1
elseif l[mid] < value
low = mid+1
else
return l[mid]
end
end
return -1
end

Recursive

function binary_search(l, value, low = 1, high = -1)
high == -1 && (high = length(l))
l==[] && (return -1)
low >= high &&
((low > high || l[low] != value) ? (return -1) : return low)
mid = int((low+high)/2)
l[mid] > value ? (return binary_search(l, value, low, mid-1))  :
l[mid] < value ? (return binary_search(l, value, mid+1, high)) :
return mid
end

[edit] Liberty BASIC

 
dim theArray(100)
for i = 1 to 100
theArray(i) = i
next i
 
print binarySearch(80,30,90)
 
wait
 
FUNCTION binarySearch(val, lo, hi)
IF hi < lo THEN
binarySearch = 0
ELSE
middle = int((hi + lo) / 2):print middle
if val < theArray(middle) then binarySearch = binarySearch(val, lo, middle-1)
if val > theArray(middle) then binarySearch = binarySearch(val, middle+1, hi)
if val = theArray(middle) then binarySearch = middle
END IF
END FUNCTION
 

[edit]

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

[edit] Lua

Iterative

function binarySearch (list,value)
local low = 1
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

Recursive

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(1,#list)
end

[edit] 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)

Output:

3
-1

[edit] Maple

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

Recursive

BinarySearch := proc( A, value, low, high )
description "recursive binary search";
if high < low then
FAIL
else
local mid := iquo( high + low, 2 );
if A[ mid ] > value then
thisproc( A, value, low, mid - 1 )
elif A[ mid ] < value then
thisproc( A, value, mid + 1, high )
else
mid
end if
end if
end proc:

Iterative

BinarySearch := proc( A, value )
description "iterative binary search";
local low, high;
 
low, high := ( lowerbound, upperbound )( A );
while low <= high do
local mid := iquo( low + high, 2 );
if A[ mid ] > value then
high := mid - 1
elif A[ mid ] < value then
low := mid + 1
else
return mid
end if
end do;
FAIL
end proc:

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

> N := 10:
> P := [seq]( ithprime( i ), i = 1 .. N ):
> BinarySearch( P, 12, 1, N ); # recursive version
FAIL
 
> BinarySearch( P, 13, 1, N ); # recursive version
6
 
> BinarySearch( Array( P ), 13, 1, N ); # make P into an array
6
 
> PP := Array( -2 .. 7, P ): # check it works if the array is not 1-based.
> BinarySearch( PP, 13 ); # iterative version
3
 
> PP[ 3 ];
13


[edit] Mathematica

Recursive

BinarySearchRecursive[x_List, val_, lo_, hi_] := 
Module[{mid = lo + Round@((hi - lo)/2)},
If[hi < lo, Return[-1]];
Return[
Which[x[[mid]] > val, BinarySearchRecursive[x, val, lo, mid - 1],
x[[mid]] < val, BinarySearchRecursive[x, val, mid + 1, hi],
True, mid]
];
]

Iterative

BinarySearch[x_List, val_] := Module[{lo = 1, hi = Length@x, mid},
While[lo <= hi,
mid = lo + Round@((hi - lo)/2);
Which[x[[mid]] > val, hi = mid - 1,
x[[mid]] < val, lo = mid + 1,
True, Return[mid]
];
];
Return[-1];
]

[edit] MATLAB

Recursive

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

Sample Usage:

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

Iterative

function mid = binarySearchIter(list,value)
 
low = 1;
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

Sample Usage:

>> binarySearchIter([1 2 3 4 5 6 6.5 7 8 9 11 18],6.5)
 
ans =
 
7

[edit] Maxima

find(L, n) := block([i: 1, j: length(L), k, p],
if n < L[i] or n > L[j] then 0 else (
while j - i > 0 do (
k: quotient(i + j, 2),
p: L[k],
if n < p then j: k - 1 elseif n > p then i: k + 1 else i: j: k
),
if n = L[i] then i else 0
)
)$
 
".."(a, b) := if a < b then makelist(i, i, a, b) else makelist(i, i, a, b, -1)$
infix("..")$
 
a: sublist(1 .. 1000, primep)$
 
find(a, 27);
0
find(a, 421);
82

[edit] MAXScript

Iterative

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

Recursive

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

[edit] Niue

Library

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)

[edit] Objeck

Iterative

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

[edit] Objective-C

Iterative

#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[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()
{
@autoreleasepool {
 
NSArray *a = @[@1, @3, @4, @5, @6, @7, @8, @9, @10];
NSLog(@"6 is at position %d", [a binarySearch:@6]); // prints 4
 
}
return 0;
}

Recursive

#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[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()
{
@autoreleasepool {
 
NSArray *a = @[@1, @3, @4, @5, @6, @7, @8, @9, @10];
NSLog(@"6 is at position %d", [a binarySearch:@6]); // prints 4
 
}
return 0;
}

Library

Works with: Mac OS X version 10.6+
#import <Foundation/Foundation.h>
 
int main()
{
@autoreleasepool {
 
NSArray *a = @[@1, @3, @4, @5, @6, @7, @8, @9, @10];
NSLog(@"6 is at position %lu", [a indexOfObject:@6
inSortedRange:NSMakeRange(0, [a count])
options:0
usingComparator:^(id x, id y){ return [x compare: y]; }]); // prints 4
 
}
return 0;
}

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

#import <Foundation/Foundation.h>
 
CFComparisonResult myComparator(const void *x, const void *y, void *context) {
return [(__bridge id)x compare:(__bridge id)y];
}
 
int main(int argc, const char *argv[]) {
@autoreleasepool {
 
NSArray *a = @[@1, @3, @4, @5, @6, @7, @8, @9, @10];
NSLog(@"6 is at position %ld", CFArrayBSearchValues((__bridge CFArrayRef)a,
CFRangeMake(0, [a count]),
(__bridge const void *)@6,
myComparator,
NULL)); // prints 4
 
}
return 0;
}

[edit] OCaml

Recursive

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

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.

[edit] Octave

Recursive

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

Iterative

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

Example of using

r = sort(discrete_rnd(10, [1:10], ones(10,1)/10));
disp(r);
binsearch_r(r, 5, 1, numel(r))
binsearch(r, 5)

[edit] ooRexx

 
data = .array~of(1, 3, 5, 7, 9, 11)
-- search keys with a number of edge cases
searchkeys = .array~of(0, 1, 4, 7, 11, 12)
say "recursive binary search"
loop key over searchkeys
pos = recursiveBinarySearch(data, key)
if pos == 0 then say "Key" key "not found"
else say "Key" key "found at postion" pos
end
say
say "iterative binary search"
loop key over searchkeys
pos = iterativeBinarySearch(data, key)
if pos == 0 then say "Key" key "not found"
else say "Key" key "found at postion" pos
end
 
::routine recursiveBinarySearch
-- NB: Rexx arrays are 1-based
use strict arg data, value, low = 1, high = (data~items)
 
-- make sure we don't go beyond the bounds
high = min(high, data~items)
-- zero indicates not found
if high < low then return 0
 
mid = (low + high) % 2
if data[mid] > value then
return recursiveBinarySearch(data, value, low, mid - 1)
else if data[mid] < value then
return recursiveBinarySearch(data, value, mid + 1, high)
-- got it!
return mid
 
::routine iterativeBinarySearch
-- NB: Rexx arrays are 1-based
use strict arg data, value, low = 1, high = (data~items)
 
-- make sure we don't go beyond the bounds
high = min(high, data~items)
-- zero indicates not found
if high < low then return 0
loop while low <= high
mid = (low + high) % 2
if data[mid] > value then
high = mid - 1
else if data[mid] < value then
low = mid + 1
else
return mid
end
return 0
 

Output:

recursive binary search
Key 0 not found
Key 1 found at postion 1
Key 4 not found
Key 7 found at postion 4
Key 11 found at postion 6
Key 12 not found

iterative binary search
Key 0 not found
Key 1 found at postion 1
Key 4 not found
Key 7 found at postion 4
Key 11 found at postion 6
Key 12 not found

[edit] Oz

Recursive

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

Iterative

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

[edit] PARI/GP

Note that, despite the name, setsearch works on sorted vectors as well as sets.

setsearch(s, n)

[edit] Pascal

Iterative

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;

Usage:

var
list: array[0 .. 9] of real;
// ...
indexof := binary_search(123, list);

[edit] Perl

Iterative

sub binary_search {
my ($array_ref, $value, $left, $right) = @_;
while ($left <= $right) {
my $middle = int(($right + $left) / 2);
if ($array_ref->[$middle] == $value) {
return 1;
}
if ($value < $array_ref->[$middle]) {
$right = $middle - 1;
} else {
$left = $middle + 1;
}
}
return 0;
}

Recursive

sub binary_search {
my ($array_ref, $value, $left, $right) = @_;
if ($right < $left) {
return 0;
}
my $middle = int(($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);
}
}

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

sub search (@a, $x --> Int) {
binary_search { $x cmp @a[$^i] }, 0, @a.end
}

Iterative

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

Recursive

Translation of: Haskell
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 }
}
}

[edit] PHP

Iterative

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

Recursive

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

[edit] PicoLisp

Recursive

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

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

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

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

[edit] 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 <= r);
mid = (l+r)/2;
if A(mid) = M then return (mid);
if A(mid) < M then
L = mid+1;
else
R = mid-1;
end;
return (lbound(A,1)-1);
end search;

[edit] Pop11

Iterative

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

Recursive

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;

[edit] PureBasic

Both recursive and iterative procedures are included and called in the code below.

#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

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

[edit] Python

[edit] Python: Iterative

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

[edit] Python: Recursive

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

[edit] Python: Library


Python's bisect module provides binary search functions

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)

[edit] Python: Alternate

Complete binary search function with python's bisect module:

from bisect import bisect_left
 
def binary_search(a, x, lo=0, hi=None): # can't use a to specify default for hi
hi = hi if hi is not None else len(a) # hi defaults to len(a)
pos = bisect_left(a,x,lo,hi) # find insertion position
return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end

[edit] Python: Approximate binary search

Returns the nearest item of list l to value.

def binary_search(l, value):
low = 0
high = len(l)-1
while low + 1 < high:
mid = (low+high)//2
if l[mid] > value:
high = mid
elif l[mid] < value:
low = mid
else:
return mid
return high if abs(l[high] - value) < abs(l[low] - value) else low

[edit] R

Recursive

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

Iterative

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
}

Example

a <- 1:100
IterBinSearch(a, 50)
BinSearch(a, 50, 1, length(a)) # output 50
IterBinSearch(a, 101) # outputs NULL

[edit] Racket

 
#lang racket
(define (binary-search x v)
 ; loop : index index -> index or #f
 ; return i s.t. l<=i<h and v[i]=x
(define (loop l h)
(cond [(>= l h) #f]
[else (define m (quotient (+ l h) 2))
(define y (vector-ref v m))
(cond
[(> y x) (loop l (- m 1))]
[(< y x) (loop (+ m 1) h)]
[else m])]))
(loop 0 (vector-length v)))
 

Examples:

(binary-search 6 #(1 3 4 5 6 7 8 9 10))  ; gives 4
(binary-search 6 #(1 3 4 5 7 8 9 10))    ; gives #f 

[edit] REXX

[edit] recursive version

Incidentally, REXX doesn't care if the values are integers (or even numbers), as long as they're in order.

(includes the extra credit)

/*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 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.*/
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(@)
avg=(word(@,1)+word(@,high))/2
loc = binarySearch(low,high)
 
if loc==-1 then do
say  ? "wasn't found in the list."
exit /*stick a fork in it, we're done.*/
end
else say  ? 'is in the list, its index is:' loc
say
say 'arithmetic mean of the' high "values=" avg
exit /*stick a fork in it, we're done.*/
/*───────────────────────────────────BINARYSEARCH subroutine────────────*/
binarySearch: procedure expose @ ?; parse arg low,high
if high<low then return -1 /*the item wasn't found in list. */
mid=(low+high)%2
y=word(@,mid)
if ?=y then return mid
if y>? then return binarySearch(low, mid-1)
return binarySearch(mid+1, high)

output when using the input of: 499.1

499.1 wasn't found in the list.

output when using the input of: 499

arithmetic mean of the 74 values= 510

499 is in the list, its index is: 41

[edit] iterative version

(includes the extra credit)

/*REXX program finds a value in a list using an iterative binary search.*/
@= 3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181,
193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401 409 421 433,
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.*/
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(@)
say 'arithmetic mean of the' high "values=" (word(@,1)+word(@,high))/2
say
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 /*stick a fork in it, we're done.*/
end
 
if y>? then high=mid-1
else low=mid+1
end /*while*/
 
say  ? "wasn't found in the list."
/*stick a fork in it, we're done.*/

output when using the input of: -314

arithmetic mean of the 79 values= 508

-314 wasn't found in the list.

output when using the input of: 619

arithmetic mean of the 79 values= 508

619 is in the list, its index is: 53

[edit] Ruby

Recursive

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
 
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]
 
[0,42,45,24324,99999].each do |val|
i = ary.binary_search(val)
if i
puts "found #{val} at index #{i}: #{ary[i]}"
else
puts "#{val} not found in array"
end
end

Iterative

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]
 
[0,42,45,24324,99999].each do |val|
i = ary.binary_search_iterative(val)
if i
puts "found #{val} at index #{i}: #{ary[i]}"
else
puts "#{val} not found in array"
end
end
Output:
found 0 at index 0: 0
42 not found in array
found 45 at index 10: 45
found 24324 at index 24: 24324
99999 not found in array

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

haystack = [0,1,4,5,6,7,8,9,12,26,45,67,78,90,98,123,211,234,456,769,865,2345,3215,14345,24324]
needles = [0,42,45,24324,99999]
 
needles.select{|needle| haystack.bsearch{|hay| needle <=> hay} } # => [0, 45, 24324]
 
Which is 60% faster than "needles & haystack".

[edit] Run BASIC

Recursive

dim theArray(100)
global theArray
for i = 1 to 100
theArray(i) = i
next i
 
print binarySearch(80,30,90)
 
FUNCTION binarySearch(val, lo, hi)
IF hi < lo THEN
binarySearch = 0
ELSE
middle = (hi + lo) / 2
if val < theArray(middle) then binarySearch = binarySearch(val, lo, middle-1)
if val > theArray(middle) then binarySearch = binarySearch(val, middle+1, hi)
if val = theArray(middle) then binarySearch = middle
END IF
END FUNCTION

[edit] Rust

Iterative

fn binary_search(haystack: ~[int], needle: int) -> int {
let mut low = 0;
let mut high = haystack.len() as int - 1;
 
if high == 0 { return -1 }
 
while low <= high {
// avoid overflow
let mid = low + (high - low) / 2;
 
if haystack[mid] > needle { high = mid - 1 }
else if haystack[mid] < needle { low = mid + 1 }
else { return mid }
}
 
return -1;
}

[edit] 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)
}

[edit] Scheme

Recursive

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

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

The calls to helper are in tail position, so since Scheme implementations support proper tail-recursion the computation proces is iterative.

[edit] Seed7

Iterative

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;

Recursive

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

[edit] 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.

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;

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.

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;

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:

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;
 

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.

[edit] Standard ML

Recursive

fun binary_search cmp (key, arr) =
let
fun aux slice =
if ArraySlice.isEmpty slice then
NONE
else
let
val mid = ArraySlice.length slice div 2
in
case cmp (ArraySlice.sub (slice, mid), key)
of LESS => aux (ArraySlice.subslice (slice, mid+1, NONE))
| GREATER => aux (ArraySlice.subslice (slice, 0, SOME mid))
| EQUAL => SOME (#2 (ArraySlice.base slice) + mid)
end
in
aux (ArraySlice.full arr)
end

Usage:

- val a = Array.fromList [2, 3, 5, 6, 8];
val a = [|2,3,5,6,8|] : int array
- binary_search Int.compare (4, a);
val it = NONE : int option
- binary_search Int.compare (8, a);
val it = SOME 4 : int option

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

Library

Works with: SML/NJ

Usage:

- structure IntArray = struct
=   open Array
=   type elem = int
=   type array = int Array.array
=   type vector = int Vector.vector
= end;
structure IntArray :
  sig
[ ... rest omitted ]
- structure IntBSearch = BSearchFn (IntArray);
structure IntBSearch :
  sig
    structure A : <sig>
    val bsearch : ('a * A.elem -> order)
                  -> 'a * A.array -> (int * A.elem) option
  end
- val a = Array.fromList [2, 3, 5, 6, 8];
val a = [|2,3,5,6,8|] : int array
- IntBSearch.bsearch Int.compare (4, a);
val it = NONE : (int * IntArray.elem) option
- IntBSearch.bsearch Int.compare (8, a);
val it = SOME (4,8) : (int * IntArray.elem) option

[edit] Tcl

ref: Tcl wiki

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

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

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

[edit] TI-83 BASIC

PROGRAM:BINSEARC
:Disp "INPUT A LIST:"
:Input L1
:SortA(L1)
:Disp "INPUT A NUMBER:"
:Input A
:1→L
:dim(L1)→H
:int(L+(H-L)/2)→M
:While L<H and L1(M)≠A
:If A>M
:Then
:M+1→L
:Else
:M-1→H
:End
:int(L+(H-L)/2)→M
:End
:If L1(M)=A
:Then
:Disp A
:Disp "IS AT POSITION"
:Disp M
:Else
:Disp A
:Disp "IS NOT IN"
:Disp L1

[edit] UnixPipes

Parallel

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

[edit] VBA

Recursive version:

Public Function BinarySearch(a, value, low, high)
'search for "value" in ordered array a(low..high)
'return index point if found, -1 if not found

If high < low Then
BinarySearch = -1 'not found
Exit Function
End If
midd = low + Int((high - low) / 2) ' "midd" because "Mid" is reserved in VBA
If a(midd) > value Then
BinarySearch = BinarySearch(a, value, low, midd - 1)
ElseIf a(midd) < value Then
BinarySearch = BinarySearch(a, value, midd + 1, high)
Else
BinarySearch = midd
End If
End Function

Here are some test functions:

Public Sub testBinarySearch(n)
Dim a(1 To 100)
'create an array with values = multiples of 10
For i = 1 To 100: a(i) = i * 10: Next
Debug.Print BinarySearch(a, n, LBound(a), UBound(a))
End Sub
 
Public Sub stringtestBinarySearch(w)
'uses BinarySearch with a string array
Dim a
a = Array("AA", "Maestro", "Mario", "Master", "Mattress", "Mister", "Mistress", "ZZ")
Debug.Print BinarySearch(a, w, LBound(a), UBound(a))
End Sub

and sample output:

stringtestBinarySearch "Master"
 3 
testBinarySearch "Master"
-1 
testBinarySearch 170
 17 
stringtestBinarySearch 170
-1 
stringtestBinarySearch "Moo"
-1 
stringtestBinarySearch "ZZ"
 7 

Iterative version:

Public Function BinarySearch2(a, value)
'search for "value" in array a
'return index point if found, -1 if not found

low = LBound(a)
high = UBound(a)
Do While low <= high
midd = low + Int((high - low) / 2)
If a(midd) = value Then
BinarySearch2 = midd
Exit Function
ElseIf a(midd) > value Then
high = midd - 1
Else
low = midd + 1
End If
Loop
BinarySearch2 = -1 'not found
End Function

[edit] 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.)

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

[edit] Visual Basic .NET

Iterative

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

Recursive

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

[edit] Wortel

Translation of: JavaScript
; Recursive
@var rec &[a v l h] [
@if < h l @return null
@var m @/ +h l 2
@? {
> `m a v @!rec[a v l -m 1]
< `m a v @!rec[a v +1 m h]
m
}
]
 
; Iterative
@var itr &[a v] [
@vars{l 0 h #-a}
@while <= l h [
@var m @/ +l h 2
@iff {
> `m a v :h -m 1
< `m a v :l +m 1
@return m
}
]
null
]
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox