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.

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

Examples

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

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

Java

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

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

PHP

Iterative

This approach uses a loop.

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

Recursive

This approach uses recursion.

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

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

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