在给定序列中查找第一个大于等于或最后一个小于等于给定值的元素

二分查找的第三个变形版本：在给定排序序列中查找第一个大于等于给定值的元素。

有了昨天的基础，来解决今天这个问题，是不是很简单？所不同的是判断节点不一样了，我们之前的需求都是查找等于给定值，现在变成了大于等于给定值，所以我们要在 nums[mid] >= num 这个判断条件上做文章，思路还是和之前两个变形版本类似，当 mid 已经是最左边的元素，或者 mid 的前一个元素值小于给定查询值，则 mid 对应元素即为满足条件的元素，否则继续往前查找。对应的 C++ 实现代码如下：

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

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;
}

同样，与之相对的，还有我们这次分享中最后要讨论的一个二分查找的变形版本：在给定序列中查找最后一个小于等于给定值的元素。

有了前面几个变形版本的铺垫，相信你自己就可以写出对应的实现代码了。这次的判断节点变成了 nums[mid] <= num，其中 num 是待查找的元素值，当 mid 已经是最后一个元素索引，或者 mid 的后一个元素值大于 num 则当前 mid 对应元素就是要查找的元素，否则要继续往后查找。

对应的 C++ 实现代码如下：

#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]) {
        if (mid == sizeof(nums) - 1 || nums[mid + 1] > num){
            return mid;
        } else {
            return binary_search_internal(nums, num, mid + 1, high);
        }
    } else if (num < nums[mid]) {
        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;
}