PHP中数组二分查找的实现
我最近一直在阅读和观看编程理论的讲座，这让我想起了我在大学学到的这个算法。二进制搜索数组是一种分治算法，它采用一个数组并通过将数组分成两半来搜索该数组中的值。算法是这样工作的。
给定一个排序数组，找到中点。
如果中点的值大于要搜索的值，则该值必须位于数组的前半部分。
如果中点的值小于要搜索的值，则该值必须位于数组的前半部分。
取有问题的数组的一半，并通过重新指向中点来重复第一步。
重复此操作，直到数组的长度为1或0。如果数组长度为1，则这就是值。如果数组的长度为0，则该值不在数组中。
有一些实现细节可以确保中间值是正确的，并避免从数组的末尾跑掉。
这是该算法在PHP中的实现。
/**
* Use binary search to find a key of a value in an array.
*
* @param array $array
* The array to search for the value.
* @param int $value
* A value to be searched.
*
* @return int|null
* Returns the key of the value in the array, or null if the value is not found.
*/
function binarySearch($array, $value) {
//将左指针设置为0。
$left = 0;
//将右指针设置为数组的长度-1。
$right = count($array) - 1;
while ($left <= $right) {
//将初始中点设置为数组长度一半的向下舍入值。
$midpoint = (int) floor(($left + $right) / 2);
if ($array[$midpoint] < $value) {
//中点值小于该值。
$left = $midpoint + 1;
} elseif ($array[$midpoint] > $value) {
//中点值大于该值。
$right = $midpoint - 1;
} else {
//这是我们正在寻找的关键。
return $midpoint;
}
}
//未找到该值。
return NULL;
}为了对这个算法运行一些测试，我运行了以下代码。所有这些都打印为真。
//生成数组。
$array = range(0, 10);
//遍历数组，搜索每个值。
foreach ($array as $key => $value) {
echo var_export(binarySearch($array, $value) === $value, TRUE) . PHP_EOL;
}
//搜索数组外的值。
echo var_export(binarySearch($array, -1) === NULL, TRUE) . PHP_EOL;
echo var_export(binarySearch($array, 11) === NULL, TRUE) . PHP_EOL;这是一个简洁的小算法，非常适合搜索排序数据的数组，其中数组的键是连续的。比简单地遍历数组以查找值要高效得多。