Binary search

From CodeCodex

Revision as of 18:04, 8 August 2006 by Jdh30 (Talk | contribs)

A binary search algorithm (or binary chop) is a technique for finding a particular value in a linear array, by ruling out half of the data at each step, widely but not exclusively used in computer science. A binary search finds the median, makes a comparison to determine whether the desired value comes before or after it, and then searches the remaining half in the same manner. A binary search is an example of a divide and conquer algorithm (more specifically a decrease and conquer algorithm) and a dichotomic search (more at Search algorithm).

Implementations

Pseudocode

This determines the index of a given value in a sorted list a between indices left and right:

function binarySearch(a, value, left, right)
    if right < left
        return not found
    mid := floor((right-left)/2)+left
    if a[mid] = value
        return mid
    if value < a[mid]
        return binarySearch(a, value, left, mid-1)
    else
        return binarySearch(a, value, mid+1, right)

Because the calls are tail-recursive, this can be rewritten as a loop, making the algorithm in-place:

function binarySearch(a, value, left, right)
    while left ≤ right
        mid := floor((right-left)/2)+left
        if a[mid] = value
            return mid
        if value < a[mid]
            right := mid-1
        else
            left  := mid+1
    return not found

In both cases, the algorithm terminates because on each recursive call or iteration, the range of indexes right minus left always gets smaller, and so must eventually become negative.

C

NOTE: This particular implementation returns -1 if the value cannot be found.

int BinarySearch(int *array, int key, int low, int high)
{
  int middle;
  if(low > high) /* termination case */
    return -1;
  middle = (low+high)/2;
  if(array[middle] == key)
    return middle;
  else if(array[middle] > key)
    return BinarySearch(array, key, low, middle-1); /* search left */
  return BinarySearch(array, key, middle+1, high); /* search right */
}

OCaml

NOTE: This particular implementation raises the Not_found exception if the value cannot be found.

# let rec search a ?(l=0) ?(u=Array.length a - 1) k =
    if l > u then raise Not_found;
    let m = l + (u - l) / 2 in
    match compare k a.(m) with
    | -1 -> search a ~l ~u:(m - 1) k
    | 1 -> search a ~l:(m + 1) ~u k
    | _ -> m;;
val search : 'a array -> ?l:int -> ?u:int -> 'a -> int = <fun>

For example:

# search [|0;1;2;3;4;5;6;7;8;9|] 3;;
- : int = 3

PHP

NOTE: This particular implementation returns -1 if the value cannot be found.

// $low and $high have to be integers

function BinarySearch( $array, $key, $low, $high )
{
    if( $low > $high ) // termination case
    {
        return -1;
    }

    $middle = intval( ( $low+$high )/2 ); // gets the middle of the array

    if ( $array[$middle] == $key ) // if the middle is our key
    {
        return $middle;
    }
    elseif ( $key < $array[$middle] ) // our key might be in the left sub-array
    {
        return BinarySearch( $array, $key, $low, $middle-1 );
    }	

    return BinarySearch( $array, $key, $middle+1, $high ); // our key might be in the right sub-array
}


Assembly

Formatted in MASM. Input: term is the term being searched for, array is the pointer to the array, and asize indicates the size of array in bytes.

bsearch proc term:DWORD,array:DWORD,asize:DWORD
	mov eax,array
	mov ecx,array
	add ecx,asize
	@@:
	cmp eax,ecx
	jg not_found
	mov edx,eax
	add edx,ecx
	shr edx,1
	xchg DWORD PTR [edx],eax
	cmp eax,term
	xchg DWORD PTR [edx],eax
	jg search_right
	jl search_left
	mov eax,edx
	sub eax,array
	ret
	search_right:
	mov ecx,edx
	jmp @B
	search_left:
	mov eax,edx
	jmp @B
	not_found:
	mov eax,-1
	ret
bsearch endp