从给定序列中查找第一个或最后一个匹配元素

符合标准的二分查找条件的序列一般是比较理想的情况，如果要查找的元素在序列中有多个怎么办？所以我们要给大家介绍的第一个常见的变形版本，就是在一个给定排序序列中查找第一个等于给定值的元素。在继续往下看之前，你不妨借机先思考一下要怎么实现。

其实关键节点就在于在序列中找到值等于待查找元素值时的处理。如果此时 mid 位置已经到了序列的最左边，不能再往左了，或者序列中索引小于 mid 的上一个元素值不等于待查找元素值，那么此时 mid 就是第一个等于待查找元素值的位置；否则还要继续往前找。

对应的 C++ 实现代码如下，其他地方都一样，就是 num == nums[mid] 时的处理逻辑变了：

#include <iostream>

int binary_search_internal(int* nums, int num, int low, int high){
    if (low > high){
        return -1;
    }
    int mid = (low + high) / 2;
    if (num < nums[mid]) {
        return binary_search_internal(nums, num, low, mid - 1);
    } else if (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);
        }
    }
}

int binary_search(int* nums, int num) {
    return binary_search_internal(nums,num,0, sizeof(nums) - 1);
}


int main() {
    int nums[] = {1,2,3,4,5,6};
    std::cout << binary_search(nums, 3) << std::endl;
    return 0;
}

既然有第一个等于给定值的查询，自然就有最后一个等于给定值的查询，这就是二分查找的第二个变形版本：在给定已排序序列中查找最后一个等于给定值的元素。实现逻辑和上面类似，只需要改动 num == nums[mid] 时的处理逻辑，只是这时的条件变成了 mid 位置到了序列的最右边，不能再往后了，或者索引大于 mid 的后一个元素值不等于带查找元素，才返回 mid，否则，还要继续往后找。在我给出实现代码之前，你能自行实现这段代码吗？不防动手写一下，或者头脑中构思下。

下面我来给出查找最后一个等于给定值的元素的 C++ 实现代码，由于其他部分都一样，我只给出 binary_search_internal 函数的代码：

int binary_search_internal(int* nums, int num, int low, int high){
    if (low > high){
        return -1;
    }
    int mid = (low + high) / 2;
    if (num < nums[mid]) {
        return binary_search_internal(nums, num, low, mid - 1);
    } else if (num > nums[mid]) {
        return binary_search_internal(nums, num, mid + 1, high);
    } else {
        if (mid == sizeof(nums) - 1 || nums[mid + 1] != num) {
            return mid;
        } else {
            return binary_search_internal(nums, num, low, mid - 1);
        }
    }
}