Binary Search

Binary search (a.k.a Half-Interval Search) algorithms finds the position of a target value within an array.



									function BinarySearch(&$data, $count, $value) {
	$low = 0; $high = $count - 1; $midpoint = 0;

	while ($low <= $high)
	{
		$midpoint = floor($low + ($high - $low) / 2);

		if ($value == $data[$midpoint])
			return $midpoint;
		else if ($value < $data[$midpoint])
			$high = $midpoint - 1;
		else
			$low = $midpoint + 1;
	}

	return -1;
}
								


Example

									$data = array();
for ($i = 0; $i < 10; $i++) {
	$data[$i] = $i * 10;
}

$value = BinarySearch($data, 10, 60);
								


Output

									6