# Binary search

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

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
@@:
cmp eax,ecx
jg not_found
mov edx,eax
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
```