c++ 二分法查找有序序列中最后一个小于等于于目标值的位置 代码

在 C++ 中，二分查找（Binary Search）通常用于已排序的数组中找到某个元素的确切位置。如果需要找到的是小于等于目标值的最大索引，可以在标准二分查找的基础上稍作修改。以下是简单的代码示例：

#include <iostream>

// 二分查找函数，返回小于等于 target 的最大索引
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果目标值大于中间元素，则在右半部分继续查找
        if (arr[mid] < target)
            left = mid + 1;
        // 否则，如果目标值小于等于中间元素，则更新左边界并检查下一个中间元素
        else
            right = mid - 1;
    }

    // 如果整个数组遍历完都没有找到满足条件的元素，返回数组长度作为插入位置
    return left;
}

int main() {
    int arr[] = {1, 3, 5, 6, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;  // 搜索的值

    int result = binarySearch(arr, 0, n - 1, target);
    if (result != -1)
        std::cout << "Last index <= " << target << ": " << result << std::endl;
    else
        std::cout << "No element found smaller than or equal to " << target << std::endl;

    return 0;
}

在这个例子中，`binarySearch` 函数会在 `arr[left...right]` 区间内寻找，当找到第一个大于 `target` 的元素时停止，并返回它的前一个位置作为结果。