Python finding numbers from a list that satisfy a specific condition [closed]

Good evening, I am currently having some problems implementing a binary search algorithm, which extracts the amount of numbers in a list that satisfy this condition

Suppose Sorted list A = [1,2,4,5,6,7,8] I need to find the amount of numbers that satisfy this condition.

Absolute(A[i] – i) <= C where C is a number specified by the user for example

|A[i] -i|<= C <—- That is the condition I need to satisfy, i need to find the amount of numbers that are in the list that fulfil this condition.

Example:

    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.

Now I realise I need to use binary search to ensure my running time is in O(log N) time, but I am not sure where do I put the condition/if statement.

Can someone please show me how this would look in python code. Thank you so much for the assistance.

Answer

Using Python Bisect module

Use a key with binary_search module to allow function evaluations

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
    

Test

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

Test c from 0 to 63

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

Output

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

Performance Testing

Compare to list comprehension (O(n) algorithm)

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])

Timing Test

Create a large random array

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

Binary search ~289X faster for n = 10, 000