python/C++二分查找库函数（lower_bound() 、upper_bound，bisect_left，bisect_right）

二分查找是一种经典的搜索算法，广泛应用于有序数据集中。它允许在大型数据集中高效地查找目标元素，减少了搜索的时间复杂度。本文将介绍在 C++ 和 Python 中内置的二分查找函数，让二分查找变得更加容易。

c++

lower_bound() 、upper_bound

定义在头文件中,
lower_bound 和 upper_bound 是 C++ STL 中与二分查找相关的两个非常有用的函数。它们都用于在有序容器中查找元素的位置。下面我将通过一个示例来详细讲解它们的用法。

假设我们有一个有序的整数数组 arr，如下所示：

#include 
#include 
#include 

int main() {
    std::vector<int> arr = {1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9};
    int target = 4;

    // 使用 lower_bound 查找目标值的第一个出现位置
    std::vector<int>::iterator lower = std::lower_bound(arr.begin(), arr.end(), target);

    // 使用 upper_bound 查找目标值的最后一个出现位置的下一个位置
    std::vector<int>::iterator upper = std::upper_bound(arr.begin(), arr.end(), target);

    // 输出结果
    std::cout << "数组中 " << target << " 的出现位置：" << std::endl;
    std::cout << "lower_bound 的结果：" << std::distance(arr.begin(), lower) << std::endl;
    std::cout << "upper_bound 的结果：" << std::distance(arr.begin(), upper) << std::endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

输出
数组中 4 的出现位置：
lower_bound 的结果：4
upper_bound 的结果：7

在上述示例中，我们使用了 lower_bound 和 upper_bound 函数来查找目标值 4 在数组中的位置。下面是这两个函数的详细解释：

• lower_bound：它返回一个迭代器，指向数组中第一个不小于目标值的元素。在我们的示例中，lower 将指向数组中第一个 4 的位置。

• upper_bound：它返回一个迭代器，指向数组中第一个大于目标值的元素。在我们的示例中，upper 将指向数组中第一个大于 4 的元素位置。

请注意，如果目标值在数组中不存在，lower 和 upper 的差值将为零，因为它们将指向同一个位置。这两个函数在查找有序容器中的范围时非常有用，帮助我们精确定位元素的位置。

python

bisect_left

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
bisect.bisect_left 函数在 Python 的 bisect 模块中用于在有序序列中查找目标值的插入位置，它接受四个参数：

a：表示有序序列，通常是一个列表。

x：表示要查找的目标值。

lo（可选）：表示搜索范围的起始位置，默认为 0。

hi（可选）：表示搜索范围的结束位置，默认为序列的长度。

下面是一个示例，演示了 bisect.bisect_left 函数的用法：

import bisect

arr = [1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]
target = 4

# 在整个序列中查找目标值的插入位置
index = bisect.bisect_left(arr, target)
print(f"在整个序列中查找 {target} 的插入位置：{index}")

# 在指定范围内查找目标值的插入位置
lo = 2  # 搜索范围的起始位置
hi = 7  # 搜索范围的结束位置
index_range = bisect.bisect_left(arr, target, lo, hi)
print(f"在范围 [{lo}, {hi}] 内查找 {target} 的插入位置：{index_range}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在上述示例中，首先我们在整个序列中查找目标值 4 的插入位置，然后在指定范围 [2, 7] 内查找 4 的插入位置。这两个插入位置的结果将告诉你如果将目标值插入到序列中，它应该出现在哪个位置。

bisect_right

bisect.bisect_right 函数与 bisect.bisect_left 函数非常类似，都用于在有序序列中查找目标值的插入位置。它们的区别在于，bisect_right 返回的位置是目标值插入后应该位于的右侧位置，而 bisect_left 返回的位置是目标值插入后应该位于的左侧位置。