python - Python从满足特定条件的列表中查找数字

Question

晚上好，我目前在实现二进制搜索算法时遇到了一些问题，该算法提取列表中满足此条件的数字数量

假设排序列表 A = [1,2,4,5,6,7,8] 我需要找到满足此条件的数字数量。

Absolute(A[i] - i) <= C 其中 C 是用户指定的数字，例如

|A[i] -i|<= C <---- 这就是我需要满足的条件，我需要找到列表中满足这个条件的数字的数量。

例子：

    A = [1, 2, 4, 8, 16, 32, 64]
    c = 4

    A[0] = | 1 - 0 |  = 1.
    A[1] = | 2 - 1 |  = 1.
    A[2] = | 4 - 2 |  = 2.
    A[3] = | 8 - 3 |  = 5.
    A[4] = | 16 - 4 | = 12.
    A[5] = | 32 - 5 | = 27.
    A[6] = | 64 - 6 | = 58.

现在我意识到我需要使用二进制搜索来确保我的运行时间在 O(log N) 时间内，但我不确定在哪里放置条件/if 语句。

有人可以告诉我这在 python 代码中的样子吗？非常感谢您的帮助。

标签： pythonalgorithmbinary

Answer 1

使用 Python Bisect 模块

使用带有 binary_search 模块的键来允许函数评估

from bisect import bisect_left

class KeyifyList(object):
    " Allows specifying a key with binary search module"
    def __init__(self, inner, key):
        self.inner = inner
        self.key = key

    def __len__(self):
        return len(self.inner)

    def __getitem__(self, k):
        return self.key((k, self.inner[k]))

def bin_search(a, c):
  # Binary search for placement
  # Using key function to allow binary search using a function
  # Computes abs(a[i] - i) at places where binary search is evaluated
  # key computes abs(a[k]-k)
  # Binary search so O(log(n)) time complexity
  i = bisect_left(KeyifyList(a, lambda kv: abs(kv[1]-kv[0])), c)

  if i == len(a):
    last_index = len(a) -1
    if abs(a[last_index] - last_index) <= c:
      return len(a)  # all indices satisfy
    else:
      i = last_index

  while i >= 0 and abs(a[i]-i) > c:
    # this is normally a one point move over
    # so O(1) rather than O(n) in time complexity
    i -= 1
  
  # number of points is one more than index to satisfy
  return i + 1
    

测试

A = [1, 2, 4, 8, 16, 32, 64]
c = 4

测试 c 从 0 到 63

for c in range(65):
  print(f'c = {c}, number of points = {bin_search(A, c)}')

输出

c = 0, number of points = 0
c = 1, number of points = 1
c = 2, number of points = 3
c = 3, number of points = 3
c = 4, number of points = 3
c = 5, number of points = 4
c = 6, number of points = 4
c = 7, number of points = 4
c = 8, number of points = 4
c = 9, number of points = 4
c = 10, number of points = 4
c = 11, number of points = 4
c = 12, number of points = 5
c = 13, number of points = 5
c = 14, number of points = 5
c = 15, number of points = 5
c = 16, number of points = 5
c = 17, number of points = 5
c = 18, number of points = 5
c = 19, number of points = 5
c = 20, number of points = 5
c = 21, number of points = 5
c = 22, number of points = 5
c = 23, number of points = 5
c = 24, number of points = 5
c = 25, number of points = 5
c = 26, number of points = 5
c = 27, number of points = 6
c = 28, number of points = 6
c = 29, number of points = 6
c = 30, number of points = 6
c = 31, number of points = 6
c = 32, number of points = 6
c = 33, number of points = 6
c = 34, number of points = 6
c = 35, number of points = 6
c = 36, number of points = 6
c = 37, number of points = 6
c = 38, number of points = 6
c = 39, number of points = 6
c = 40, number of points = 6
c = 41, number of points = 6
c = 42, number of points = 6
c = 43, number of points = 6
c = 44, number of points = 6
c = 45, number of points = 6
c = 46, number of points = 6
c = 47, number of points = 6
c = 48, number of points = 6
c = 49, number of points = 6
c = 50, number of points = 6
c = 51, number of points = 6
c = 52, number of points = 6
c = 53, number of points = 6
c = 54, number of points = 6
c = 55, number of points = 6
c = 56, number of points = 6
c = 57, number of points = 6
c = 58, number of points = 7
c = 59, number of points = 7
c = 60, number of points = 7
c = 61, number of points = 7
c = 62, number of points = 7
c = 63, number of points = 7
c = 64, number of points = 7

性能测试

与列表理解比较（O(n) 算法）

def list_comprehension_method(a, c):
  " Use list comprehension to find number of points "
  return len([1 for i, v in enumerate(A) if abs(v - i) <= c])

计时测试

创建一个大的随机数组

n = 10000   # number of points in array
c = n // 4  # c value
A = sorted([randint(1, n) for _ in range(n)])

print(timeit(lambda: bin_search(A, c), number=100))
# Time: 0.00173 seconds
print(timeit(lambda: list_comprehension_method(A, c), number=100))
# Time: 0.49982 seconds

对于 n = 10, 000，二分搜索快了 ~289X