Binary search

From Rosetta Code

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
  }

Contents 1 Ada 1.1 Recursive 1.2 Iterative 2 BASIC 2.1 Recursive 2.2 Iterative 3 C++ 3.1 Recursive 3.2 Iterative 4 Common Lisp 4.1 Iterative 4.2 Recursive 5 D 5.1 Recursive 5.2 Iterative 6 Forth 7 Fortran 7.1 Recursive 7.2 Iterative 8 Haskell 9 Java 9.1 Iterative 9.2 Recursive 10 MAXScript 10.1 Iterative 10.2 Recursive 11 OCaml 11.1 Recursive 12 Perl 12.1 Iterative 12.2 Recursive 13 PHP 13.1 Iterative 13.2 Recursive 14 Pop11 14.1 Iterative 14.2 Recursive 15 Python 15.1 Iterative 15.2 Recursive 16 Seed7 16.1 Iterative 16.2 Recursive 17 UnixPipes 17.1 Parallel

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

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

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

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

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

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

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

[edit] Common Lisp

[edit] Iterative

(defun">defun binary-search (value array)
  (let ((low 0)
        (high (1- (length">length">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)))))))

[edit] Recursive

(defun">defun binary-search (value array &optional (low 0) (high (1- (length">length">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

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

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

[edit] Iterative

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 
}

[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

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

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

[edit] Iterative

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

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

[edit] MAXScript

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

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

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

[edit] Perl

[edit] Iterative

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

[edit] Recursive

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

[edit] PHP

[edit] Iterative

 
function binary_search( $secret, $start, $end )
{
        do
        {
                $guess = $start + ( ( $end - $start ) / 2 );
 
                if ( $guess > $secret )
                        $end = $guess;
 
                if ( $guess < $secret )
                        $start = $guess;
 
        } while ( $guess != $secret );
 
        return $guess;
}
 

[edit] Recursive

 
function binary_search( $secret, $start, $end )
{
        $guess = $start + ( ( $end - $start ) / 2 );
 
        if ( $guess > $secret )
                return (binary_search( $secret, $start, $guess ));
 
        if ( $guess < $secret )
                return (binary_search( $secret, $guess, $end ) );
 
        return $guess;
}
 

[edit] Pop11

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

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

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

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

[edit] Seed7

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

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

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