I'm trying to find number of positive numbers in list using python and i want the code to run in O(log(n)) the list is of type Positive-Negative if there's negative number they will be in the right hand side of the list and all the positives is in the left side. for example if the input is :
lst=[2,6,0,1,-3,-19]
the output is
4
I've tried some methods but i didn't get the result that i wanted this is last form that i get until now:
def pos_neg(lst):
if int(len(lst)) is 0 or (int(len(lst)) is 1 and lst[0] <0):
return 0
elif len(lst) is 1 and lst[0] >=0:
return 1
leng = (int(len(lst))) // 2
counter = 0
index = 0
while(leng != 0):
if lst[leng] >=0 and lst[leng+1] <0:
index = leng
break
if lst[leng] >=0 and lst[leng + 1] >=0:
if int(len(lst)) < leng + int(len(lst)):
return 0
else:
leng = (leng + int(len(lst))) // 2
if lst[leng] <0 and lst[leng + 1] <0:
leng = leng // 2
return index
You can use recursion. Every time the list is halved, so the complexity is O(logn)
def find_pos(start, end, l, count):
if(start > end):
return count
middle = start + (end-start)//2
if(l[middle] >= 0): # that means all left side is positive
count += (middle-start) + 1
return find_pos(middle+1, end, l, count)
else: # that means I am in wrong region
return find_pos(start, middle-1, l, count)
lst=[2,6,0,1,-3,-19]
find_pos(0, len(lst)-1, lst, 0)
>>> 4
Update: If you want one function passing only lst
def find_positives(l):
return find_pos(0, len(l)-1, l, 0)
find_positives(lst)
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments