PHP binary search example code for recursive and non-recursive implementations

Binary search Also known as half search, the advantage is that the number of comparisons is less, the search speed is fast, and the average performance is good; its disadvantage is that the table to be looked up is required to be an ordered table, and insertionDeletiondifficulty. Therefore, the binary search method is suitable for ordered lists that do not change frequently but are searched frequently. First, assuming that the elements in the table are arranged in ascending order, compare the keyword recorded in the middle position of the table with the search keyword. If the two are equal, the search is successful; otherwise, use the middle position record to divide the table into two sub-tables, the first and last. If If the keyword recorded in the middle position is greater than the search keyword, then the previous sub-table will be searched further, otherwise the next sub-table will be searched further. Repeat the above process until a record that meets the conditions is found, making the search successful, or until the subtable does not exist, in which case the search fails.

The basic idea of ​​binary search is to divide n elements into two roughly equal parts, compare a[n/2] with x, if x=a[n/2], find x, algorithm Abort; if Search the right half of array a for x.The following is the example code

// 递归二分查找
$arr = [1,2,3,4,11,12,124,1245];
function bin_recur_find($arr, $beg, $end, $v) {
	if ($beg <= $end) {
		$idx = floor(($beg + $end)/2);
		if ($v == $arr[$idx]) {
			return $idx;
		} else {
			if ($v < $arr[$idx]) {
				return bin_recur_find($arr, $beg, $idx - 1, $v);
			} else {
				return bin_recur_find($arr, $idx + 1, $end, $v);
			}
		}
	}
	return -1;
}
// 非递归二分查找
function bin_find($arr, $v) {
	$beg = 0;
	$end = count($arr) - 1;
	while ($beg <= $end) {
		$idx = floor(($beg + $end)/2);
		if ($v == $arr[$idx]) {
			return $idx;
		} else {
			if ($v < $arr[$idx]) {
				$end = $idx - 1;
			} else {
				$beg = $idx + 1;
			}
		}
	}
	return -1;
}

echo bin_recur_find($arr, 0, count($arr) - 1, 100) . "\n";
echo bin_find($arr, 100) . "\n";

The above is the detailed content of PHP binary search example code for recursive and non-recursive implementations. For more information, please follow other related articles on the PHP Chinese website!