二分查找第一个元素的位置

Java的lower_bound函数

lower_bound是找到第一个大于等于value的位置，比如 [1, 2, 3, 3, 3, 4, 7, 8] 查找 3 会返回下标为2的位置，查找 6 会返回下标为6的位置。如果未找到则返回数组的长度（C++中会返回end()迭代器的位置）。

public int lower_bound(int[] nums, int begin, int end, int value) {
    while (begin < end) {
        int mid = begin + (end - begin) / 2;
        if (nums[mid] < value) {
            begin = mid + 1;
        } else {
            end = mid;
        }
    }
    return begin;
}

Java的upper_bound函数

upper_bound 会去寻找大于value的位置，比如 [1, 2, 3, 3, 3, 4, 7, 8] 查找 3 会返回下标为5的位置，查找 6 会返回下标为6的位置。

public int upper_bound(int[] nums, int begin, int end, int value) {
    while (begin < end) {
        int mid = begin + (end - begin) / 2;
        if (nums[mid] <= value) {
            begin = mid + 1;
        } else {
            end = mid;
        }
    }
    return begin;
}

赏

谢谢你请我吃糖果

微信