python - 获取区域包围的第一个和最后一个值的索引

Question

我有一个排序的 pytables 整数值表，它可能包含重复项，以及一个由开始和结束值(结束独占)表示的区域。

我想找到最接近区域开始的值的索引和最接近区域结束的值的索引。结果索引必须包含在区域中。示例:

region = (35, 56)
table_data = [4, 6, 18, 18, 30, 37, 37, 49, 54, 56, 80, 84]

result: (5, 8)

这听起来像是可以用类似于二进制搜索的算法来解决的问题，但我还没有想出如何去做。

由于这段代码可能在非常大的 pytables 表上执行数千次，因此性能很重要。最好，如果可能的话，开始和结束索引值应该在同一个循环中计算。

有人能帮忙吗？

编辑:

我实际上不是在使用数组，而是使用 pytables 表。所以建议使用 bisect 模块的答案是行不通的。行可以通过表[索引]访问(通过表的getslice方法)

Answer 1

简单使用binsearch查找

• 大于下限的最小值
• 小于上限的最大值

复杂度为 O(lgn)，因为这是两个完全独立的问题。