返回主页

二分查找右边界

手动实现二分查找，在升序数组 a[1..n] 中查找 x 最后一次出现的位置，时间复杂度 O(log n)

算法模板发布于 2026/09/07#二分#二分查找
C++11 行312 Bytes
下载文件
// 若找到，返回下标（1‑based）；否则返回 -1
int binarySearchRight(int a[], int n, int x) {
    if (n <= 0) return -1;
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return (a[l] == x) ? l : -1;
}