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.
Advertisement
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