二分查找及变种(参考C++标准库)

C++标准库二分查找的相关的函数

lower_bound和upper_bound都是求下边界的,即查找满足x >= target或者x > target,最小的x的位置。求上边界(查找满足x < target或者x <= target,最大的x的位置),可以调用互补的求下边界的函数再减一,例如x >= target的下边界减一就是x < target的上边界,所以C++标准库只提供了求下边界的两个函数。

lower_bound和upper_bound的两个版本的实现只有一个if条件是不同的,其他的都相同,用左闭右开的搜索区间[first, last),first = mid + 1, last = mid,不用多写+1或者-1,while (first < last),跳出循环后first和last相等。

下面实现5个函数:
1. 查找等于目标值(x == target)的位置
2. 查找大于等于目标值(x >= target)的最小的位置
3. 查找大于目标值(x > target)的最小的位置
4. 查找小于目标值(x < target)的最大的位置
5. 查找小于等于目标值(x <= target)的最大的位置

1. 查找等于目标值(x == target)的位置

2. 查找大于等于目标值(x >= target)的最小的位置

3. 查找大于目标值(x > target)的最小的位置

4. 查找小于目标值(x < target)的最大的位置

5. 查找小于等于目标值(x <= target)的最大的位置

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注