Binary search: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added PicoLisp)
No edit summary
Line 491: Line 491:
The <code>binary_search()</code> function returns true or false for whether an element equal to the one you want exists in the array. It does not give you any information as to where it is.
The <code>binary_search()</code> function returns true or false for whether an element equal to the one you want exists in the array. It does not give you any information as to where it is.
<lang cpp>bool found = std::binary_search(array, array+len, what); // a custom comparator can be given as fourth arg</lang>
<lang cpp>bool found = std::binary_search(array, array+len, what); // a custom comparator can be given as fourth arg</lang>
=={{header|C sharp|C#}}==
<lang csharp>using System;


namespace BinarySearch
{
class Program
{
static void Main(string[] args)
{

int[] a = new int[] { 2, 4, 6, 8, 9 };
Console.WriteLine(BinarySearchIterative(a, 9));
Console.WriteLine(BinarySearchRecursive(a, 9, 0, a.Length));
}

private static int BinarySearchIterative(int[] a, int val){
int low = 0;
int high = a.Length;
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] > val)
high = mid-1;
else if (a[mid] < val)
low = mid+1;
else
return mid;
}
return -1;
}

private static int BinarySearchRecursive(int[] a, int val, int low, int high)
{
if (high < low)
return -1;
int mid = (low + high) / 2;
if (a[mid] > val)
return BinarySearchRecursive(a, val, low, mid - 1);
else if (a[mid] < val)
return BinarySearchRecursive(a, val, mid + 1, high);
else
return mid;
}
}
}</lang>
=={{header|Clojure}}==
=={{header|Clojure}}==


Revision as of 09:11, 15 May 2010

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 host 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, one normally would start by choosing the range's midpoint as the guess, and then asking whether the guess was higher, lower, or equal to the secret number. If the guess was too high, one would select the point exactly between the range midpoint and the beginning of the range. If the original guess was too low, one would ask about the point exactly between the range midpoint and the end of the range. This process repeats until one has reached the secret number.

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

Recursive Pseudocode: 

  BinarySearch(A[0..N-1], value, low, high) {
      if (high < low)
          return not_found
      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) {
          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
  }

Ada

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

procedure Test_Recursive_Binary_Search is 

  Not_Found : exception;
  
  generic
     type Index is range <>;
     type Element is private;
     type Array_Of_Elements is array (Index range <>) of Element;
     with function "<" (L, R : Element) return Boolean is <>;
  function Search (Container : Array_Of_Elements; Value : Element) return Index;

  function Search (Container : Array_Of_Elements; Value : Element) return Index is
     Mid : Index;
  begin
     if Container'Length > 0 then
        Mid := (Container'First + Container'Last) / 2;
        if Value < Container (Mid) then
           if Container'First /= Mid then
              return Search (Container (Container'First..Mid - 1), Value);
           end if;
        elsif Container (Mid) < Value then
           if Container'Last /= Mid then
              return Search (Container (Mid + 1..Container'Last), Value);
           end if;
        else
           return Mid;
        end if;
     end if;
     raise Not_Found;
  end Search;

  type Integer_Array is array (Positive range <>) of Integer;
  function Find is new Search (Positive, Integer, Integer_Array);
  
  procedure Test (X : Integer_Array; E : Integer) is
  begin
     New_Line;
     for I in X'Range loop
        Put (Integer'Image (X (I)));
     end loop;
     Put (" contains" & Integer'Image (E) & " at" & Integer'Image (Find (X, E)));
  exception
     when Not_Found =>
        Put (" does not contain" & Integer'Image (E));
  end Test;

begin 

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

end Test_Recursive_Binary_Search;</lang> Iterative <lang ada>with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Binary_Search is 

  Not_Found : exception;
  
  generic
     type Index is range <>;
     type Element is private;
     type Array_Of_Elements is array (Index range <>) of Element;
     with function "<" (L, R : Element) return Boolean is <>;
  function Search (Container : Array_Of_Elements; Value : Element) return Index;

  function Search (Container : Array_Of_Elements; Value : Element) return Index is
     Low  : Index := Container'First;
     High : Index := Container'Last;
     Mid  : Index;
  begin
     if Container'Length > 0 then
        loop
           Mid := (Low + High) / 2;
           if Value < Container (Mid) then
              exit when Low = Mid;
              High := Mid - 1;
           elsif Container (Mid) < Value then
              exit when High = Mid;
              Low := Mid + 1;
           else
              return Mid;
           end if;
        end loop;
     end if;
     raise Not_Found;
  end Search;

  type Integer_Array is array (Positive range <>) of Integer;
  function Find is new Search (Positive, Integer, Integer_Array);
  
  procedure Test (X : Integer_Array; E : Integer) is
  begin
     New_Line;
     for I in X'Range loop
        Put (Integer'Image (X (I)));
     end loop;
     Put (" contains" & Integer'Image (E) & " at" & Integer'Image (Find (X, E)));
  exception
     when Not_Found =>
        Put (" does not contain" & Integer'Image (E));
  end Test;

begin 

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

end Test_Binary_Search;</lang> Sample output: 

 2 4 6 8 9 contains 2 at 1
 2 4 6 8 9 does not contain 1
 2 4 6 8 9 contains 8 at 4
 2 4 6 8 9 does not contain 10
 2 4 6 8 9 contains 9 at 5
 2 4 6 8 9 does not contain 5

ALGOL 68

Iterative <lang algol68>MODE ELEMENT = STRING;

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

);</lang> Recursive <lang algol68>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

);</lang> Test cases: <lang algol68>ELEMENT needle = "mister"; []ELEMENT hay stack = ("AA","Maestro","Mario","Master","Mattress","Mister","Mistress","ZZ"), 

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

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

   FOR case TO UPB test cases DO
       ELEMENT needle = test cases[case];
       INT index = search(hay stack, needle);
       BOOL found = ( index <= 0 | FALSE | hay stack[index]=needle);
       printf(($""""g""" "b("FOUND at","near")" index "dl$, needle, found, index))
   OD;

test search(iterative binary search, test cases); test search(recursive binary search, test cases)</lang> Output:<lang algol68>"A" near index 1 "Master" FOUND at index 4 "Monk" near index 8 "ZZZ" near index 8</lang>

AutoHotkey

<lang AutoHotkey>array := "1,2,4,6,8,9" StringSplit, A, array, `,  ; creates associative array MsgBox % x := BinarySearch(A, 4, 1, A0) ; Recursive MsgBox % A%x% MsgBox % x := BinarySearchI(A, A0, 4)  ; Iterative MsgBox % A%x%

BinarySearch(A, value, low, high) { ; A0 contains length of array 

 If (high < low)               ; A1, A2, A3...An are array elements
   Return not_found
 mid := Floor((low + high) / 2)
 If (A%mid% > value) ; A%mid% is automatically global since no such locals are present
   Return BinarySearch(A, value, low, mid - 1)
 Else If (A%mid% < value)
   Return BinarySearch(A, value, mid + 1, high)
 Else
   Return mid

}

BinarySearchI(A, lengthA, value) { 

 low := 0
 high := lengthA - 1
 While (low <= high) {
   mid := Floor((low + high) / 2) ; round to lower integer
   If (A%mid% > value)   
     high := mid - 1
   Else If (A%mid% < value)
     low := mid + 1
   Else
     Return mid
 }
 Return not_found

}</lang>

BASIC

Recursive

Works with: FreeBASIC
Works with: RapidQ

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

 DIM middle AS Integer
 
 IF hi < lo THEN
   binary_search = 0
 ELSE
   middle = (hi + lo) / 2
   SELECT CASE value
     CASE IS < array(middle)

binary_search = binary_search(array(), value, lo, middle-1) 

     CASE IS > array(middle)

binary_search = binary_search(array(), value, middle+1, hi) 

     CASE ELSE

binary_search = middle 

   END SELECT
 END IF

END FUNCTION </lang>

Iterative

Works with: FreeBASIC
Works with: RapidQ

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

 DIM middle AS Integer
 
 WHILE lo <= hi
   middle = (hi + lo) / 2
   SELECT CASE value
     CASE IS < array(middle)

hi = middle - 1 

     CASE IS > array(middle)

lo = middle + 1 

     CASE ELSE

binary_search = middle EXIT FUNCTION 

   END SELECT
 WEND
 binary_search = 0

END FUNCTION </lang>

Testing the function

The following program can be used to test both recursive and iterative version. <lang freebasic> SUB search (array() AS Integer, value AS Integer) 

 DIM idx AS Integer

 idx = binary_search(array(), value, LBOUND(array), UBOUND(array))
 PRINT "Value "; value;
 IF idx < 1 THEN
   PRINT " not found"
 ELSE
   PRINT " found at index "; idx
 END IF

END SUB

DIM test(1 TO 10) AS Integer DIM i AS Integer

DATA 2, 3, 5, 6, 8, 10, 11, 15, 19, 20 FOR i = 1 TO 10 ' Fill the test array 

 READ test(i)

NEXT i

search test(), 4 search test(), 8 search test(), 20 </lang>

Output: 

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

C

Iterative <lang c>/* http://www.solipsys.co.uk/b_search/spec.htm */ typedef int Object;

int cmpObject(Object* pa, Object *pb) { 

 Object a = *pa;
 Object b = *pb;
 if (a < b) return -1;
 if (a == b) return 0;
 if (a > b) return 1;
 assert(0);

}

int bsearch(Object Array[], int n, Object *KeyPtr, int (*cmp)(Object *, Object *), 

           int NotFound)

{ 

 unsigned left = 1, right = n; /* `unsigned' to avoid overflow in `(left + right)/2' */

 if ( ! (Array && n > 0 && KeyPtr && cmp)) 
   return NotFound; /* invalid input or empty array */

 while (left < right)
 {
   /* invariant: a[left] <= *KeyPtr <= a[right] or *KeyPtr not in Array */
   unsigned m = (left  +  right) / 2; /*NOTE: *intentionally* truncate for odd sum */
   
   if (cmp(Array + m, KeyPtr) < 0) 
     left = m + 1;       /* a[m] < *KeyPtr <= a[right] or *KeyPtr not in Array */
   else 
     /* assert(right != m) or infinite loop possible */
     right = m;          /* a[left] <= *KeyPtr <= a[m] or *KeyPtr not in Array */
 }
 /* assert(left == right) */
 return (cmp(Array + right, KeyPtr) == 0) ? right : NotFound;

}</lang>

Example: <lang c>#define DUMMY -1 /* dummy element of array (to adjust indexing from 1..n) */

int main(void) { 

 Object a[] = {DUMMY, 0, 1, 1, 2, 5}; /* allowed indices from 1 to n including */
 int n = sizeof(a)/sizeof(*a) - 1;
 const int NotFound = -1;

 /* key not in Array */
 Object key = 4;
 assert(NotFound == bsearch(a, n, &key, cmpObject, NotFound));
 key = DUMMY;
 assert(NotFound == bsearch(a, n, &key, cmpObject, NotFound));
 key = 7;
 assert(NotFound == bsearch(a, n, &key, cmpObject, NotFound));

 /* all possible `n' and `k' for `a' array */
 int k;
 key = 10; /* not in `a` array */
 for (n = 0; n <= sizeof(a)/sizeof(*a) - 1; ++n)
   for (k = n; k>=1; --k) {
     int index = bsearch(a, n, &a[k], cmpObject, NotFound);
     assert(index == k || (k==3 && index == 2) || n == 0); /* for equal `1's */
     assert(NotFound == bsearch(a, n, &key, cmpObject, NotFound));
   }
 n = sizeof(a)/sizeof(*a) - 1;

 /* NULL array */
 assert(NotFound == bsearch(NULL, n, &key, cmpObject, NotFound));
 /* NULL &key */
 assert(NotFound == bsearch(a, n, NULL, cmpObject, NotFound));
 /* NULL cmpObject */
 assert(1 == bsearch(a, n, &a[1], cmpObject, NotFound));
 assert(NotFound  == bsearch(a, n, &a[1], NULL, NotFound));

 printf("OK\n");
 return 0;

}</lang>

Library <lang c>#include <stdlib.h> /* for bsearch */

  1. include <stdio.h>

int intcmp(const void *a, const void *b) { 

   /* this is only correct if it doesn't overflow */
   return *(const int *)a - *(const int *)b;

}

int main() { 

   int nums[5] = {2, 3, 5, 6, 8};
   int desired = 6;
   int *ptr = bsearch(&desired, nums, 5, sizeof(int), intcmp);
   if (ptr == NULL)
       printf("not found\n");
   else
       printf("index = %d\n", ptr - nums);

   return 0;

}</lang>

C++

Recursive <lang cpp>template <class T> int binsearch(const T array[], int len, T what) { 

 if (len == 0) return -1;
 int mid = len / 2;
 if (array[mid] == what) return mid;
 if (array[mid] < what) {
   int result = binsearch(array+mid+1, len-(mid+1), what);
   if (result == -1) return -1;
   else return result + mid+1;
 }
 if (array[mid] > what)
   return binsearch(array, mid, what);

}

  1. include <iostream>

int main() { 

 int array[] = {2, 3, 5, 6, 8};
 int result1 = binsearch(array, sizeof(array)/sizeof(int), 4),
     result2 = binsearch(array, sizeof(array)/sizeof(int), 8);
 if (result1 == -1) std::cout << "4 not found!" << std::endl;
 else std::cout << "4 found at " << result1 << std::endl;
 if (result2 == -1) std::cout << "8 not found!" << std::endl;
 else std::cout << "8 found at " << result2 << std::endl;

 return 0;

}</lang>

Iterative <lang cpp>template <class T> int binSearch(const T arr[], int len, T what) { 

 int low = 0;
 int high = len - 1;
 while (low <= high) {
   int mid = (low + high) / 2;
   if (arr[mid] > what)
     high = mid - 1;
   else if (arr[mid] < what)
     low = mid + 1;
   else
     return mid;
 }
 return -1; // indicate not found

}</lang>

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

The lower_bound() function returns an iterator to the first position where a value could be inserted without violated without violating the order; i.e. the first element equal to the element you want, or the place where it would be inserted. <lang cpp>int *ptr = std::lower_bound(array, array+len, what); // a custom comparator can be given as fourth arg</lang>

The upper_bound() function returns an iterator to the last position where a value could be inserted without violated without violating the order; i.e. one past the last element equal to the element you want, or the place where it would be inserted. <lang cpp>int *ptr = std::upper_bound(array, array+len, what); // a custom comparator can be given as fourth arg</lang>

The equal_range() function returns a pair of the results of lower_bound() and upper_bound(). <lang cpp>std::pair<int *, int *> bounds = std::equal_range(array, array+len, what); // a custom comparator can be given as fourth arg</lang> Note that the difference between the bounds is the number of elements equal to the element you want.

The binary_search() function returns true or false for whether an element equal to the one you want exists in the array. It does not give you any information as to where it is. <lang cpp>bool found = std::binary_search(array, array+len, what); // a custom comparator can be given as fourth arg</lang>

C#

<lang csharp>using System;

namespace BinarySearch { 

   class Program
   {
       static void Main(string[] args)
       {

           int[] a = new int[] { 2, 4, 6, 8, 9 };
           Console.WriteLine(BinarySearchIterative(a, 9));
           Console.WriteLine(BinarySearchRecursive(a, 9, 0, a.Length));
       }

       private static int BinarySearchIterative(int[] a, int val){
           int low = 0;
           int high = a.Length;
           while (low <= high)
           {
               int mid = (low + high) / 2;
               if (a[mid] > val)
                   high = mid-1;
               else if (a[mid] < val)
                   low = mid+1;
               else
                   return mid;
           }
           return -1;
       }

       private static int BinarySearchRecursive(int[] a, int val, int low, int high)
       {
           if (high < low)
               return -1;
           int mid = (low + high) / 2;
           if (a[mid] > val)
               return BinarySearchRecursive(a, val, low, mid - 1);
           else if (a[mid] < val)
               return BinarySearchRecursive(a, val, mid + 1, high);
           else
               return mid;
       }
   }

}</lang>

Clojure

Recursive <lang clojure>(defn bsearch 

 ([coll t]
   (bsearch coll 0 (dec (count coll)) t))
 ([coll l u t]
   (if (> l u) -1
     (let [m (quot (+ l u) 2) mth (nth coll m)]
       (cond
         ; the middle element is greater than t
         ; so search the lower half
         (> mth t) (recur coll l (dec m) t)
         ; the middle element is less than t
         ; so search the upper half
         (< mth t) (recur coll (inc m) u t)
         ; we've found our target
         ; so return its index
         (= mth t) m)))))</lang>

Common Lisp

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

 (let ((low 0)
       (high (1- (length array))))
   
   (do () ((< high low) nil)
     (let ((middle (floor (/ (+ low high) 2))))
       
       (cond ((> (aref array middle) value)
              (setf high (1- middle)))
             
             ((< (aref array middle) value)
              (setf low (1+ middle)))
             
             (t (return middle)))))))</lang>

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

 (if (< high low)
     nil
     (let ((middle (floor (/ (+ low high) 2))))
       
       (cond ((> (aref array middle) value)
              (binary-search value array low (1- middle)))
             
             ((< (aref array middle) value)
              (binary-search value array (1+ middle) high))
             
             (t middle)))))</lang>

D

Recursive

The range criterion is omitted because arrays in D can be slices of other arrays, so in a way every array is potentially a range.

<lang d>size_t binsearch(T) (T[] array, T what) { 

 size_t shift(size_t what, int by) {
   if (what == size_t.max) return size_t.max;
   return what + by;
 }
 if (!array.length) return size_t.max;
 auto mid = array.length / 2;
 if (array[mid] == what) return mid;
 if (array[mid] < what)
   return shift(binsearch(array[mid+1 .. $], what), mid + 1);
 if (array[mid] > what)
   return binsearch(array[0 .. mid], what);

}

import std.stdio; void main() { 

 auto array = [2, 3, 5, 6, 8], result1 = array.binsearch(4), result2 = array.binsearch(8);
 if (result1 == size_t.max) writefln("4 not found!");
 else writefln("4 found at ", result1);
 if (result2 == size_t.max) writefln("8 not found!");
 else writefln("8 found at ", result2);

}</lang> Iterative <lang d>size_t binSearch(T)(T[] arr, T what) { 

 size_t low = 0 ;
 size_t high = arr.length - 1 ;
 while (low <= high) {
   size_t mid = (low + high) / 2 ;
   if(arr[mid] > what)
     high = mid - 1 ;
   else if(arr[mid] < what)
    low = mid + 1 ;
   else
    return mid ;                       {
 }
 return size_t.max ; // indicate not found

}</lang>

E

<lang e>/** Returns null if the value is not found. */ def binarySearch(collection, value) { 

   var low := 0
   var high := collection.size() - 1
   while (low <= high) {
       def mid := (low + high) // 2
       def comparison := value.op__cmp(collection[mid])
       if      (comparison.belowZero()) { high := mid - 1 } \
       else if (comparison.aboveZero()) { low := mid + 1 }  \
       else if (comparison.isZero())    { return mid }      \
       else                             { throw("You expect me to binary search with a partial order?") }
   }
   return null

}</lang>

Factor

Factor already includes a binary search in its standard library. The following code offers an interface compatible with the requirement of this task, and returns either the index of the element if it has been found or f otherwise. <lang factor>USING: binary-search kernel math.order ;

binary-search ( seq elt -- index/f )
   [ [ <=> ] curry search ] keep = [ drop f ] unless ;</lang>

Forth

This version is designed for maintaining a sorted array. If the item is not found, then then location returned is the proper insertion point for the item. This could be used in an optimized Insertion sort, for example. <lang forth>defer (compare) ' - is (compare) \ default to numbers

cstr-compare ( cstr1 cstr2 -- <=> ) \ counted strings
 swap count rot count compare ;
mid ( u l -- mid ) tuck - 2/ -cell and + ;
bsearch ( item upper lower -- where found? )
 rot >r
 begin  2dup >
 while  2dup mid
        dup @ r@ (compare)
        dup
 while  0<
        if   nip cell+   ( upper mid+1 )
        else rot drop swap ( mid lower )
        then
 repeat drop nip nip             true
 else   max ( insertion-point ) false
 then
 r> drop ;

create test 2 , 4 , 6 , 9 , 11 , 99 ,

probe ( n -- ) test 5 cells bounds bsearch . @ . cr ;

1 probe \ 0 2 2 probe \ -1 2 3 probe \ 0 4 10 probe \ 0 11 11 probe \ -1 11 12 probe \ 0 99</lang>


Fortran

Recursive In ISO Fortran 90 or later use a RECURSIVE function and ARRAY SECTION argument: <lang fortran>recursive function binarySearch_R (a, value) result (bsresult) 

   real, intent(in) :: a(:), value
   integer          :: bsresult, mid
   
   mid = size(a)/2 + 1
   if (size(a) == 0) then
       bsresult = 0        ! not found
   else if (a(mid) > value) then
       bsresult= binarySearch_R(a(:mid-1), value)
   else if (a(mid) < value) then
       bsresult = binarySearch_R(a(mid+1:), value)
       if (bsresult /= 0) then
           bsresult = mid + bsresult
       end if
   else
       bsresult = mid      ! SUCCESS!!
   end if

end function binarySearch_R</lang>

Iterative In ISO Fortran 90 or later use an ARRAY SECTION POINTER: <lang fortran>function binarySearch_I (a, value) 

   integer                  :: binarySearch_I
   real, intent(in), target :: a(:)
   real, intent(in)         :: value
   real, pointer            :: p(:)
   integer                  :: mid, offset
   
   p => a
   binarySearch_I = 0
   offset = 0
   do while (size(p) > 0)
       mid = size(p)/2 + 1
       if (p(mid) > value) then
           p => p(:mid-1)
       else if (p(mid) < value) then
           offset = offset + mid
           p => p(mid+1:)
       else
           binarySearch_I = offset + mid    ! SUCCESS!!
           return
       end if
   end do

end function binarySearch_I</lang>

Haskell

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

<lang haskell>binarySearch :: Integral a => (a -> Ordering) -> (a, a) -> Maybe a binarySearch p (low,high) 

 | high < low = Nothing
 | otherwise = 
     let mid = (low + high) `div` 2 in 
     case p mid of
       LT -> binarySearch p (low, mid-1)
       GT -> binarySearch p (mid+1, high)
       EQ -> Just mid</lang>

Application to an array:

<lang haskell>import Data.Array

binarySearchArray :: (Ix i, Integral i, Ord e) => Array i e -> e -> Maybe i binarySearchArray a x = binarySearch p (bounds a) where 

 p m = x `compare` (a ! m)</lang>

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

HicEst

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

  array = NINT( RAN(n) )
  SORT(Vector=array, Sorted=array)
  x = NINT( RAN(n) )

  idx = binarySearch( array, x )
  WRITE(ClipBoard) x, "has position ", idx, "in ", array
END

FUNCTION binarySearch(A, value) 

  REAL :: A(1), value

  low = 1
  high = LEN(A)
  DO i = 1, high
    IF( low > high) THEN
      binarySearch = 0
      RETURN
    ELSE
      mid = INT( (low + high) / 2 )
      IF( A(mid) > value) THEN
        high = mid - 1
      ELSEIF( A(mid) < value ) THEN
        low = mid + 1
      ELSE
        binarySearch = mid
        RETURN
      ENDIF
    ENDIF
  ENDDO
END</lang>

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

Icon and Unicon

Icon

Only a recursive solution is shown here. <lang icon>procedure binsearch(A, target) 

   if *A = 0 then fail
   mid := *A/2 + 1
   if target > A[mid] then {
       return mid + binsearch(A[(mid+1):0], target)
       }
   else if target < A[mid] then {
       return binsearch(A[1+:(mid-1)], target)
       }
   return mid

end</lang> A program to test this is: <lang icon>procedure main(args) 

   target := integer(!args) | 3
   every put(A := [], 1 to 18 by 2)

   outList("Searching", A)
   write(target," is ",("at "||binsearch(A, target)) | "not found")

end

procedure outList(prefix, A) 

   writes(prefix,": ")
   every writes(!A," ")
   write()

end</lang> with some sample runs: 

->bins 0
Searching: 1 3 5 7 9 11 13 15 17 
0 is not found
->bins 1
Searching: 1 3 5 7 9 11 13 15 17 
1 is at 1
->bins 2
Searching: 1 3 5 7 9 11 13 15 17 
2 is not found
->bins 3
Searching: 1 3 5 7 9 11 13 15 17 
3 is at 2
->bins 16
Searching: 1 3 5 7 9 11 13 15 17 
16 is not found
->bins 17
Searching: 1 3 5 7 9 11 13 15 17 
17 is at 9
->bins 7
Searching: 1 3 5 7 9 11 13 15 17 
7 is at 4
->bins 9
Searching: 1 3 5 7 9 11 13 15 17 
9 is at 5
->bins 10
Searching: 1 3 5 7 9 11 13 15 17 
10 is not found
->

Unicon

The Icon solution also works in Unicon.

J

J already includes a binary search primitive (I.). The following code offers an interface compatible with the requirement of this task, and returns either the index of the element if it has been found or 'Not Found' otherwise: <lang j>bs=. , 'Not Found'"_^:({:@[ -.@-: ] { }:@[) I.</lang> Examples: <lang j> (2, 3, 5, 6, 8, 10, 11, 15, 19, 20) bs 11 6 

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

Not Found</lang>

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

Iterative <lang j> 'X Y L H M'=. i.5 NB. Setting mnemonics for boxes f=. &({::) NB. Fetching the contents of a box o=. @: NB. Composing verbs (functions)

boxes=. ; , a: $~ 3: NB. Appending 3 (empty) boxes to the inputs LowHigh=. (0 ; # o (X f)) (L,H)} ] NB. Setting the low and high bounds midpoint=. < o (<. o (2 %~ L f + H f)) M} ] NB. Updating the midpoint case=. >: o * o (Y f - M f { X f) NB. Less=0, equal=1, or greater=2

squeeze=. (< o (_1 + M f) H} ])`(< o _: L} ])`(< o (1 + M f) L} ])@.case return=. (M f) o ((<@:('Not Found'"_) M} ]) ^: (_ ~: L f))

bs=. return o (squeeze o midpoint ^: (L f <: H f) ^:_) o LowHigh o boxes</lang> Recursive <lang j> 'X Y L H M'=. i.5 NB. Setting mnemonics for boxes f=. &({::) NB. Fetching the contents of a box o=. @: NB. Composing verbs (functions)

boxes=. a: ,~ ; NB. Appending 1 (empty) box to the inputs midpoint=. < o (<. o (2 %~ L f + H f)) M} ] NB. Updating the midpoint case=. >: o * o (Y f - M f { X f) NB. Less=0, equal=1, or greater=2

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

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

Java

Iterative <lang java>... //check will be the number we are looking for //nums will be the array we are searching through int hi = nums.length - 1; int lo = 0; int guess = (hi + lo) / 2; while((nums[guess] != check) && (hi > lo)){ 

       if(nums[guess] > check){
               hi = guess - 1;
       }else if(nums[guess] < check){
               lo = guess + 1;
       }
       guess = (hi + lo) / 2;

} if(hi < lo){ 

       System.out.println(check + " not in array");

}else{ 

       System.out.println("found " + nums[guess] + " at index " + guess);

} ...</lang>

Recursive <lang java>public static void main(String[] args){ 

       int[] searchMe;
       int someNumber;
       ...
       int index = binarySearch(searchMe, someNumber, 0, searchMe.length);
       System.out.println(someNumber + ((index == -1) ? " is not in the array" : (" is at index " + index)));
       ...

}

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

       if(hi < lo){
               return -1; //impossible index for "not found"
       }
       int guess = (hi + lo) / 2;
       if(nums[guess] > check){
               return binarySearch(nums, check, lo, guess - 1);
       }else if(nums[guess]<check){
               return binarySearch(nums, check, guess + 1, hi);
       }
       return guess;

}</lang>

Library When the key is not found, the following functions return ~insertionPoint (the bitwise complement of the index where the key would be inserted, which is guaranteed to be a negative number).

For arrays: <lang java>import java.util.Arrays;

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

// for objects, also optionally accepts an additional comparator argument: int index = Arrays.binarySearch(array, thing, comparator); int index = Arrays.binarySearch(array, startIndex, endIndex, thing, comparator);</lang>

For Lists: <lang java>import java.util.Collections;

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

JavaScript

A straightforward implementation of the pseudocode

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

   if (hi < lo)
       return null;
   var mid = Math.floor((lo+hi)/2);
   if (a[mid] > value)
       return binary_search_recursive(a, value, lo, mid-1);
   else if (a[mid] < value)
       return binary_search_recursive(a, value, mid+1, hi);
   else
       return mid;

}</lang>

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

   lo = 0;
   hi = a.length - 1;
   while (lo <= hi) {
       var mid = Math.floor((lo+hi)/2);
       if (a[mid] > value)
           hi = mid - 1;
       else if (a[mid] < value)
           lo = mid + 1;
       else
           return mid;
   }
   return null;

}</lang>

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

 if :upper < :lower [output []]
 localmake "mid int (:lower + :upper) / 2
 if item :mid :a > :value [output bsearch :value :a :lower :mid-1]
 if item :mid :a < :value [output bsearch :value :a :mid+1 :upper]
 output :mid

end</lang>

lua

Iterative <lang lua>function binarySearch (list,value) 

   local low = 0
   local high = #list
   local mid = 0
   while low <= high do
       mid = math.floor((low+high)/2)
       if list[mid] > value then high = mid - 1
       else if list[mid] < value then low = mid + 1
            else return mid
            end
       end
   end
   return false

end</lang> Recursive <lang lua>function binarySearch (list, value) 

   local function search(low, high)
       local mid = math.floor((low+high)/2)
       if list[mid] > value then return search(low,mid-1) end
       if list[mid] < value then return search(mid+1,high) end
       return mid
   end
   return search(0,#list)

end</lang>


M4

<lang M4>define(`notfound',`-1')dnl define(`midsearch',`ifelse(defn($1[$4]),$2,$4, `ifelse(eval(defn($1[$4])>$2),1,`binarysearch($1,$2,$3,decr($4))',`binarysearch($1,$2,incr($4),$5)')')')dnl define(`binarysearch',`ifelse(eval($4<$3),1,notfound,`midsearch($1,$2,$3,eval(($3+$4)/2),$4)')')dnl dnl define(`setrange',`ifelse(`$3',`',$2,`define($1[$2],$3)`'setrange($1,incr($2),shift(shift(shift($@))))')')dnl define(`asize',decr(setrange(`a',1,1,3,5,7,11,13,17,19,23,29)))dnl dnl binarysearch(`a',5,1,asize) binarysearch(`a',8,1,asize)</lang>

Output: 

3
-1

MAXScript

Iterative <lang maxscript>fn binarySearchIterative arr value = ( 

   lower = 1
   upper = arr.count
   while lower <= upper do
   (
       mid = (lower + upper) / 2
       if arr[mid] > value then
       (
           upper = mid - 1
       )
       else if arr[mid] < value then
       (
           lower = mid + 1
       )
       else
       (
           return mid
       )
   )
   -1

)

arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10) result = binarySearchIterative arr 6</lang>

Recursive <lang maxscript>fn binarySearchRecursive arr value lower upper = ( 

   if lower == upper then
   (
       if arr[lower] == value then
       (
           return lower
       )
       else
       (
           return -1
       )
   )
   mid = (lower + upper) / 2
   if arr[mid] > value then
   (
       return binarySearchRecursive arr value lower (mid-1)
   )
   else if arr[mid] < value then
   (
       return binarySearchRecursive arr value (mid+1) upper
   )
   else
   (
       return mid
   )

)

arr = #(1, 3, 4, 5, 6, 7, 8, 9, 10) result = binarySearchRecursive arr 6 1 arr.count</lang>

Niue

Library <lang ocaml>1 2 3 4 5 3 bsearch . ( => 2 ) 5 bsearch . ( => 0 ) 'sam 'tom 'kenny ( must be sorted before calling bsearch ) sort .s ( => kenny sam tom ) 'sam bsearch . ( => 1 ) 'tom bsearch . ( => 0 ) 'kenny bsearch . ( => 2 ) 'tony bsearch . ( => -1) </lang>

OCaml

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

 if high = low then
   if a.(low) = value then
     low
   else
     raise Not_found
 else let mid = (low + high) / 2 in
   if a.(mid) > value then
     binary_search a value low (mid - 1)
   else if a.(mid) < value then
     binary_search a value (mid + 1) high
   else
     mid</lang>

Output: 

# let arr = [|1; 3; 4; 5; 6; 7; 8; 9; 10|];;
val arr : int array = [|1; 3; 4; 5; 6; 7; 8; 9; 10|]
# binary_search arr 6 0 (Array.length arr - 1);;
- : int = 4
# binary_search arr 2 0 (Array.length arr - 1);;
Exception: Not_found.

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

Octave

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

 if ( high < low )
   i = 0;
 else
   mid = floor((low + high) / 2);
   if ( array(mid) > val )
     i = binsearch_r(array, val, low, mid-1);
   elseif ( array(mid) < val ) 
     i = binsearch_r(array, val, mid+1, high);
   else
     i = mid;
   endif
 endif

endfunction</lang>

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

 low = 1;
 high = numel(array);
 i = 0;
 while ( low <= high )
   mid = floor((low + high)/2);
   if (array(mid) > value) 
     high = mid - 1;
   elseif (array(mid) < value)
     low = mid + 1;
   else
     i = mid;
     return;
   endif
 endwhile

endfunction</lang>

Example of using <lang octave>r = sort(discrete_rnd(10, [1:10], ones(10,1)/10)); disp(r); binsearch_r(r, 5, 1, numel(r)) binsearch(r, 5)</lang>

Oz

Recursive <lang oz>declare 

 fun {BinarySearch Arr Val}
    fun {Search Low High}
       if Low > High then nil
       else
          Mid = (Low+High) div 2
       in
          if Val < Arr.Mid then {Search Low Mid-1}
          elseif Val > Arr.Mid then {Search Mid+1 High}
          else [Mid]
          end
       end
    end
 in
    {Search {Array.low Arr} {Array.high Arr}}
 end

 A = {Tuple.toArray unit(2 3 5 6 8)}

in 

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

Iterative <lang oz>declare 

 fun {BinarySearch Arr Val}
    Low = {NewCell {Array.low Arr}}
    High = {NewCell {Array.high Arr}}
 in
    for while:@Low =< @High  return:Return  default:nil do
       Mid = (@Low + @High) div 2
    in
       if Val < Arr.Mid then High := Mid-1
       elseif Val > Arr.Mid then Low := Mid+1
       else {Return [Mid]}
       end
    end
 end

 A = {Tuple.toArray unit(2 3 5 6 8)}

in 

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

Perl

Iterative <lang perl>sub binary_search { 

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

}</lang>

Recursive <lang perl>sub binary_search { 

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

}</lang>

Perl 6

Works with: Rakudo version #23 "Lisbon"

With either of the below implementations of binary_search, one could write a function to search any object that does Positional this way:

<lang perl6>sub search (@a, Num $x --> Int) { 

   binary_search { $x <=> @a[$^i] }, 0, @a.end

}</lang>

Iterative <lang perl6>sub binary_search (&p, Int $lo is copy, Int $hi is copy --> Int) { 

   until $lo > $hi {
       my Int $mid = ($lo + $hi) div 2;
       given p $mid {
           when -1 { $hi = $mid - 1; } 
           when  1 { $lo = $mid + 1; }
           default { return $mid;    }
       }
   }
   fail;

}</lang>

Recursive

Translation of: Haskell

<lang perl6>sub binary_search (&p, Int $lo, Int $hi --> Int) { 

   $lo <= $hi or fail;
   my Int $mid = ($lo + $hi) div 2;
   given p $mid {
       when -1 { binary_search &p, $lo,      $mid - 1 } 
       when  1 { binary_search &p, $mid + 1, $hi      }
       default { $mid                                 }
   }

}</lang>

PHP

Iterative <lang php>function binary_search( $array, $secret, $start, $end ) { 

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

               if ( $array[$guess] > $secret )
                       $end = $guess;

               if ( $array[$guess] < $secret )
                       $start = $guess;

               if ( $end < $start)
                       return -1;

       } while ( $array[$guess] != $secret );

       return $guess;

}</lang> Recursive <lang php>function binary_search( $array, $secret, $start, $end ) { 

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

       if ( $end < $start)
               return -1;

       if ( $array[$guess] > $secret )
               return (binary_search( $array, $secret, $start, $guess ));

       if ( $array[$guess] < $secret )
               return (binary_search( $array, $secret, $guess, $end ) );

       return $guess;

}</lang>

PicoLisp

Recursive <lang PicoLisp>(de recursiveSearch (Val Lst Len) 

  (unless (=0 Len)
     (let (N (inc (/ Len 2))  L (nth Lst N))
        (cond
           ((= Val (car L)) Val)
           ((> Val (car L))
              (recursiveSearch Val (cdr L) (- Len N)) )
           (T (recursiveSearch Val Lst (dec N))) ) ) ) )</lang>

Output: 

: (recursiveSearch 5 (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9)
-> 5
: (recursiveSearch '(a b) (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9)
-> (a b)
: (recursiveSearch (9) (2 3 5 8 "abc" "klm" "xyz" (7) (a b)) 9)
-> NIL

Iterative <lang PicoLisp>(de iterativeSearch (Val Lst Len) 

  (use (N L)
     (loop
        (T (=0 Len))
        (setq
           N (inc (/ Len 2))
           L (nth Lst N) )
        (T (= Val (car L)) Val)
        (if (> Val (car L))
           (setq Lst (cdr L)  Len (- Len N))
           (setq Len (dec N)) ) ) ) )</lang>

Output: 

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

PL/I

<lang PL/I> /* A binary search of list A for element M */ search: procedure (A, M) returns (fixed binary); 

  declare (A(*), M) fixed binary;
  declare (l, r, mid) fixed binary;

  l = lbound(a,1)-1; r = hbound(A,1)+1;
  do while (l+1 < r);
     mid = (l+r)/2;
     if A(mid) = M then return (mid);
     if A(mid) < M then
        L = mid;
     else
        R = mid;
  end;
  return (lbound(A,1)-1);

end search; </lang>

Pop11

Iterative

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

   lvars low = 1, high = length(A), mid;
   while low <= high do
       (low + high) div 2 -> mid;
       if A(mid) > value then
           mid - 1 -> high;
       elseif A(mid) < value then
           mid + 1 -> low;
       else
           return(mid);
       endif;
   endwhile;
   return("not_found");

enddefine;

/* Tests */ lvars A = {2 3 5 6 8};

BinarySearch(A, 4) => BinarySearch(A, 5) => BinarySearch(A, 8) =></lang>

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

   define do_it(low, high);
       if high < low then
           return("not_found");
       endif;
       (low + high) div 2 -> mid;
       if A(mid) > value then
           do_it(low, mid-1);
       elseif A(mid) < value then
           do_it(mid+1, high);
       else
           mid;
       endif;
   enddefine;
   do_it(1, length(A));

enddefine;</lang>

PureBasic

Both recursive and iterative procedures are included and called in the code below. <lang PureBasic>#Recursive = 0 ;recursive binary search method

  1. Iterative = 1 ;iterative binary search method
  2. 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


  1. NumElements = 9 ;zero based count

Dim test(#NumElements)

DataSection 

 Data.i 2, 3, 5, 6, 8, 10, 11, 15, 19, 20

EndDataSection

fill the test array

For i = 0 To #NumElements 

 Read test(i)

Next


If OpenConsole() 

 PrintN("Recursive search:")
 search(test(), 4, #Recursive)
 search(test(), 8, #Recursive)
 search(test(), 20, #Recursive)

 PrintN("")
 PrintN("Iterative search:")
 search(test(), 4, #Iterative)
 search(test(), 8, #Iterative)
 search(test(), 20, #Iterative)

 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
 Input()
 CloseConsole()

EndIf</lang> Sample output: 

Recursive search:
  Value 4 not found
  Value 8 found at index 4
  Value 20 found at index 9

Iterative search:
  Value 4 not found
  Value 8 found at index 4
  Value 20 found at index 9

Python

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

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

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

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

Library Python's bisect module provides binary search functions <lang python>index = bisect.bisect_left(list, item) # leftmost insertion point index = bisect.bisect_right(list, item) # rightmost insertion point index = bisect.bisect(list, item) # same as bisect_right

  1. same as above but actually insert the item into the list at the given place:

bisect.insort_left(list, item) bisect.insort_right(list, item) bisect.insort(list, item)</lang>

R

Recursive

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

 if ( high < low ) {
   return(NULL)
 } else {
   mid <- floor((low + high) / 2)
   if ( A[mid] > value )
     BinSearch(A, value, low, mid-1)
   else if ( A[mid] < value )
     BinSearch(A, value, mid+1, high)
   else
     mid
 }

}</lang>

Iterative

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

 low = 1
 high = length(A)
 i = 0
 while ( low <= high ) {
   mid <- floor((low + high)/2)
   if ( A[mid] > value )
     high <- mid - 1
   else if ( A[mid] < value )
     low <- mid + 1
   else
     return(mid)
 }
 NULL

}</lang>

Example

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


Ruby

Recursive

<lang ruby>class Array 

 def binary_search(val, low=0, high=(length - 1))
   return nil if high < low
   mid = (low + high) / 2
   case
     when self[mid] > val then binary_search(val, low, mid-1)
     when self[mid] < val then binary_search(val, mid+1, high)
     else mid
   end
 end

end

def do_a_binary_search(val, ary, method) 

 i = ary.send(method, val)
 if i
   puts "found #{val} at index #{i}: #{ary[i]}"
 else
   puts "#{val} not found in array"
 end

end

ary = [0,1,4,5,6,7,8,9,12,26,45,67,78,90,98,123,211,234,456,769,865,2345,3215,14345,24324] do_a_binary_search(45, ary, :binary_search) do_a_binary_search(42, ary, :binary_search)</lang>

Iterative

<lang ruby>class Array 

 def binary_search_iterative(val)
   low, high = 0, length - 1
   while low <= high
     mid = (low + high) / 2
     case
       when self[mid] > val then high = mid - 1
       when self[mid] < val then low = mid + 1
       else return mid
     end
   end
   nil
 end

end

do_a_binary_search(45, ary, :binary_search_iterative) do_a_binary_search(42, ary, :binary_search_iterative)</lang>

Scala

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

 def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {
   case _ if high < low => None
   case mid if a(mid) > v => recurse(low, mid - 1)
   case mid if a(mid) < v => recurse(mid + 1, high)
   case mid => Some(mid)
 }
 recurse(0, a.size - 1)

}</lang>

Scheme

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

 (let helper ((low 0)
              (high (- (vector-length vector) 1)))
   (if (< high low)
       #f
       (let ((middle (quotient (+ low high) 2)))
         
         (cond ((> (vector-ref vector middle) value)
                (helper low (- middle 1)))
               
               ((< (vector-ref vector middle) value)
                (helper (+ middle 1) high))
               
               (else middle))))))</lang>

Example: 

> (binary-search 6 '#(1 3 4 5 6 7 8 9 10))
4
> (binary-search 2 '#(1 3 4 5 6 7 8 9 10))
#f

Scheme requires proper tail-recursion; so this is effectively the same as iteration.

Seed7

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

 result
   var integer: result is 0;
 local
   var integer: low is 1;
   var integer: high is 0;
   var integer: middle is 0;
 begin
   high := length(arr);
   while result = 0 and low <= high do
     middle := low + (high - low) div 2;
     if aKey < arr[middle] then
       high := pred(middle);
     elsif aKey > arr[middle] then
       low := succ(middle);
     else
       result := middle;
     end if;
   end while;
 end func;</lang>

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

 result
   var integer: result is 0;
 begin
   if low <= high then
     result := (low + high) div 2;
     if aKey < arr[result] then
       result := binarySearch(arr, aKey, low, pred(result)); # search left
     elsif aKey > arr[result] then
       result := binarySearch(arr, aKey, succ(result), high); # search right
     end if;
   end if;
 end func;

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

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

Tcl

ref: Tcl wiki <lang tcl>proc binSrch {lst x} { 

   set len [llength $lst]
   if {$len == 0} {
       return -1
   } else {
       set pivotIndex [expr {$len / 2}]
       set pivotValue [lindex $lst $pivotIndex]
       if {$pivotValue == $x} {
           return $pivotIndex
       } elseif {$pivotValue < $x} {
           set recursive [binSrch [lrange $lst $pivotIndex+1 end] $x]
           return [expr {$recursive > -1 ? $recursive + $pivotIndex + 1 : -1}]
       } elseif {$pivotValue > $x} {
           set recursive [binSrch [lrange $lst 0 $pivotIndex-1] $x]
           return [expr {$recursive > -1 ? $recursive : -1}]
       }
   }

} proc binary_search {lst x} { 

   if {[set idx [binSrch $lst $x]] == -1} {
       puts "element $x not found in list"
   } else {
       puts "element $x found at index $idx"
   }

}</lang> Note also that, from Tcl 8.4 onwards, the lsearch command includes the -sorted option to enable binary searching of Tcl lists. <lang tcl>proc binarySearch {lst x} { 

   set idx [lsearch -sorted -exact $lst $x]
   if {$idx == -1} {
       puts "element $x not found in list"
   } else {
       puts "element $x found at index $idx"
   }

}</lang>

UnixPipes

Parallel <lang bash>splitter() { 

  a=$1; s=$2; l=$3; r=$4;
  mid=$(expr ${#a[*]} / 2);
  echo $s ${a[*]:0:$mid} > $l
  echo $(($mid + $s)) ${a[*]:$mid} > $r

}

bsearch() { 

  (to=$1; read s arr; a=($arr);
      test  ${#a[*]} -gt 1  && (splitter $a $s >(bsearch $to) >(bsearch $to)) || (test "$a" -eq "$to" && echo $a at $s)
  )

}

binsearch() { 

  (read arr; echo "0 $arr" | bsearch $1)

}

echo "1 2 3 4 6 7 8 9" | binsearch 6</lang>

Vedit macro language

Iterative

For this implementation, the numbers to be searched must be stored in current edit buffer, one number per line. (Could be for example a csv table where the first column is used as key field.) <lang vedit>// Main program for testing BINARY_SEARCH

  1. 3 = Get_Num("Value to search: ")

EOF

  1. 2 = Cur_Line // hi
  2. 1 = 1 // lo

Call("BINARY_SEARCH") Message("Value ") Num_Type(#3, NOCR) if (Return_Value < 1) { 

   Message(" not found\n")

} else { 

   Message(" found at index ") Num_Type(Return_Value)

} return

BINARY_SEARCH:

while (#1 <= #2) { 

   #12 = (#1 + #2) / 2
   Goto_Line(#12)
   #11 = Num_Eval()
   if (#3 == #11) {
       return(#12)             // found
   } else {
       if (#3 < #11) {
           #2 = #12-1
       } else {
           #1 = #12+1
       }
   }

} return(0) // not found</lang>

Visual Basic .NET

Iterative <lang vbnet>Function BinarySearch(ByVal A() As Integer, ByVal value As Integer) As Integer 

   Dim low As Integer = 0
   Dim high As Integer = A.Length - 1
   Dim middle As Integer = 0

   While low <= high
       middle = (low + high) / 2
       If A(middle) > value Then
           high = middle - 1
       ElseIf A(middle) < value Then
           low = middle + 1
       Else
           Return middle
       End If
   End While

   Return Nothing

End Function</lang>

Recursive <lang vbnet>Function BinarySearch(ByVal A() As Integer, ByVal value As Integer, ByVal low As Integer, ByVal high As Integer) As Integer 

   Dim middle As Integer = 0

   If high < low Then
       Return Nothing
   End If

   middle = (low + high) / 2

   If A(middle) > value Then
       Return BinarySearch(A, value, low, middle - 1)
   ElseIf A(middle) < value Then
       Return BinarySearch(A, value, middle + 1, high)
   Else
       Return middle
   End If

End Function</lang>

Retrieved from "https://rosettacode.org/wiki/Binary_search?oldid=41494"