`bisect` 是 Python 内置模块，用于有序序列的插入和查找，下面详细介绍其功能和使用方法： #### 查找功能 `bisect` 模块提供了几个用于查找元素插入位置的函数： - `bisect(array, item)`：等同于 `bisect_right`，返回 `item` 在 `array` 中应该插入的位置，使得 `array` 仍然保持有序。如果 `item` 已经存在于 `array` 中，返回该元素右侧的位置。 - `bisect_left(array, item)`：返回 `item` 在 `array` 中应该插入的最左位置，使得 `array` 仍然保持有序。如果 `item` 已经存在于 `array` 中，返回该元素的位置。 - `bisect_right(array, item)`：返回 `item` 在 `array` 中应该插入的最右位置，使得 `array` 仍然保持有序。如果 `item` 已经存在于 `array` 中，返回该元素右侧的位置。 示例代码如下： ```python import bisect arr = [1, 3, 3, 6, 8, 12, 15] value = 3 idx_left = bisect.bisect_left(arr, value) print(idx_left) idx_right = bisect.bisect_right(arr, value) print(idx_right) ``` 在上述代码中，`bisect_left` 返回 `3` 第一次出现的位置，而 `bisect_right` 返回 `3` 最后一次出现位置的下一个位置。 #### 插入功能 `bisect` 模块还提供了几个用于插入元素的函数： - `insort(array, item)`：等同于 `insort_right`，将 `item` 插入到 `array` 中合适的位置，使得 `array` 仍然保持有序。 - `insort_left(array, item)`：将 `item` 插入到 `array` 中合适的最左位置，使得 `array` 仍然保持有序。 - `insort_right(array, item)`：将 `item` 插入到 `array` 中合适的最右位置，使得 `array` 仍然保持有序。 示例代码如下： ```python import bisect test = [1, 2, 6, 8, 19] bisect.insort(test, 10) print(test) bisect.insort_left(test, 3) print(test) bisect.insort_right(test, 7) print(test) ``` 在上述代码中，`insort`、`insort_left` 和 `insort_right` 分别将元素插入到合适的位置，保持列表的有序性。 #### 别名关系 `bisect` 是 `bisect_right` 方法的一个引用，同理 `insort` 是 `insort_right` 方法的引用 [^2]。 #### 特殊应用场景 在查询一个有序的数组中有多少个 `>` 或 `<` 某个值的时候，`bisect` 函数效率很高。例如，以下代码计算了满足条件的组合数： ```python import bisect n = int(input()) a = list(map(int, input().split())) b = list(map(int, input().split())) c = list(map(int, input().split())) a.sort() c.sort() ans = 0 for i in range(n): x = bisect.bisect_left(a, b[i]) y = len(c) - bisect.bisect_right(c, b[i]) ans += x * y print(ans) ```