日常开发过程中，除了我们昨天讲到的正常的二分查找，还有很多二分查找的变形版本，今天开始，我们就来给大家一一介绍这些变形版本。符合标准的二分查找条件的序列一般是比较理想的情况，如果要查找的元素在序列中有多个怎么办？所以我们要给大家介绍的第一个常见的变形版本，就是在一个给定排序序列中查找第一个等于给定值的元素。在继续往下看之前，你不妨借机先思考一下要怎么实现。
其实关键节点就在于在序列中找到值等于待查找元素值时的处理。如果此时 $mid 位置已经到了序列的最左边，不能再往左了，或者序列中索引小于 $mid 的上一个元素值不等于待查找元素值，那么此时 $mid 就是第一个等于待查找元素值的位置；否则还要继续往前找。
对应的 PHP 实现代码如下，其他地方都一样，就是 $num == $nums[$mid] 时的处理逻辑变了（超出评论字符限制，拆分成两部分）：
<?php
/**
* 二分查找变形版：查找第一个值等于给定值的元素（数组中包含重复数据）
*/
function binary_search($nums, $num)
{
if (count($nums) <= 1) {
return 0;
}
return binary_search_internal($nums, $num, 0, count($nums) - 1);
}
function binary_search_internal($nums, $num, $low, $high)
{
if ($low > $high) {
return -1;
}
$mid = floor(($low + $high) / 2);
if ($num < $nums[$mid]) {
return binary_search_internal($nums, $num, $low, $mid - 1);
} elseif ($num > $nums[$mid]) {
return binary_search_internal($nums, $num, $mid + 1, $high);
} else {
if ($mid == 0 || $nums[$mid-1] != $num) {
return $mid;
} else {
return binary_search_internal($nums, $num, $low, $mid - 1);
}
}
}
$nums = [1, 2, 3, 3, 4, 5, 6];
$index = binary_search($nums, 3);
print $index;
既然有第一个等于给定值的查询，自然就有最后一个等于给定值的查询，这就是二分查找的第二个变形版本：在给定已排序序列中查找最后一个等于给定值的元素。实现逻辑和上面类似，只需要改动 $num == $nums[$mid] 时的处理逻辑，只是这时的条件变成了 $mid 位置到了序列的最右边，不能再往后了，或者索引大于 $mid 的后一个元素值不等于带查找元素，才返回 $mid，否则，还要继续往后找。在我给出实现代码之前，你能自行实现这段代码吗？不防动手写一下，或者头脑中构思下。
下面我来给出查找最后一个等于给定值的元素的 PHP 实现代码，由于其他部分都一样，我只给出 binary_search_internal 函数的代码：
function binary_search_internal($nums, $num, $low, $high)
{
if ($low > $high) {
return -1;
}
$mid = floor(($low + $high) / 2);
if ($num < $nums[$mid]) {
return binary_search_internal($nums, $num, $low, $mid - 1);
} elseif ($num > $nums[$mid]) {
return binary_search_internal($nums, $num, $mid + 1, $high);
} else {
if ($mid == count($nums) - 1 || $nums[$mid + 1] != $num) {
return $mid;
} else {
return binary_search_internal($nums, $num, $mid + 1, $high);
}
}
}