如何计算排序列表中两个值之间的元素？

Question

我有一个sorted list。例如，my list 是：

my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

实际上，我有我的 class 和 int property 的对象列表，列表是根据这些列表排序的。

我想计算在 two values.

之间具有 this property 值的对象的数量

我正在寻找以下 python 等价物。

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

  std::cout << "MY_RESULT IS" << (up - v.begin())  - (low- v.begin()) << '\n';

  return 0;
}

Answer 1

我会使用 bisect 模块（因为它使用二进制搜索，给它一个 O(log n) 复杂度） 对两边进行二等分，像这样：

my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

import bisect

def find_ge(a, low, high):
    i = bisect.bisect_left(a, low)
    g = bisect.bisect_right(a, high)
    if i != len(a) and g != len(a):
        return a[i:g]
    raise ValueError

输出：

>>>find_ge(my_list, 3, 6)
[3, 4, 5, 6]

如何计算排序列表中两个值之间的元素？

How to count elements between two values in sorted list?

python

sorting

binary-search

lower-bound

python-2.7