PHPBuilder - Binary Search Algorithm



RSS Twitter
Snippets Algorithms

Binary Search Algorithm

by: jayon crow
|
March 21, 2007

Version: 2.0

Type: Function

Category: Algorithms

License: GNU General Public License

Description: Binary search algorithm function. Takes an array as an argument and the element to be searched for in the array. Returns '1' if found, '0' if not. The code can be modified slightly to return the array index of the found element.



/* Author: J.B.Lamer, Date: 20070321
 *
 * binarysearch performs a search on an already sorted (by value) array
 * returns false on not found ( check with '===' )
 * and position otherwise
 */
function binarysearch( $haystack, $needle )
{
	if ( !is_array($haystack) )
	{	return false; }
	$btm = 0;
	$top = count($haystack)-1;
	// just in case not a normal array, but is sorted properly
	$keys = array_keys($haystack);
	while ( $btm <= $top )
	{
		$pivot = floor(($btm+$top)/2);
		if ( $needle == $haystack[$keys[$pivot]] )
		{	return $keys[$pivot]; }
		elseif ( $needle < $haystack[$keys[$pivot]] )
		{	$top = $pivot-1; }
		else
		{	$btm = $pivot+1; }
	}
	return false;
}

Comment and Contribute

Your comment has been submitted and is pending approval.

Author:
jayon crow

Comment:



Comment:

(Maximum characters: 1200). You have characters left.