dificulty solving a code in O(logn)
I wrote a function that gets as an input a list of unique ints in order,(from small to big). Im supposed to find in the list an index that matches the value in the index. for example if L[2]==2 the output is true. so after i did that in complexity O(logn) i now want to find how many indexes behave like that in the given list with the same complexity O(logn). im uploading my first code that does the first part and the second code which i need help with:
def steady_state(L):
lower= 0
upper= len(L) -1
while lower<=upper:
middle_i= (upper+ lower)//2
if L[middle_i]== middle_i:
return middle_i
elif L[middle_i]>middle_i:
upper= middle_i-1
else:
lower= middle_i +1
return None
def cnt_steady_states(L):
lower= 0
upper= len(L) -1
a=b=steady_state(L)
if steady_state(L)== None:
return 0
else:
cnt=1
while True:
if L[upper] == upper and a<=upper:
cnt+= upper-a
upper= a
if L[lower]== lower and b>=lower:
cnt+= b- lower
lower = b
It's not possible with the restrictions you've given yet. The best complexity you can theoretically achieve is O(n).
O() assumes the worst case (just a definition, you could drop that part). And in the worst case you will always have to look at each item in order to check it for being equal to its index.
The case changes if you have more restrictions (eg the numbers are all ints and none may appear more than once, ie no two consecutive numbers are equal). Maybe this is the case?
EDIT:
After hearing that in fact my assumed restrictions apply (ie only once-appearing ints) I now propose this approach: You can safely assume that you can have only exactly one continuous range where all your matching entries are located. I. e. you only need to find a lower bound and upper bound. The wanted result will then be the size of that range.
Each bound can safely be found using a binary search, of which each has O(log n).
def binsearch(field, lower=True, a=0, b=None):
if b is None:
b = len(field)
while a + 1 < b:
c = (a + b) / 2
if lower:
if field[c] < c:
a = c
else:
b = c
else: # search for upper bound
if field[c] > c:
b = c
else:
a = c
return b if lower else a
def indexMatchCount(field):
upper = binsearch(field, lower=False)
lower = binsearch(field, b=upper+1)
return upper - lower + 1
This I used for testing:
field = list({ random.randint(-10, 30) for i in range(30) })
field.sort()
upper = binsearch(field, lower=False)
lower = binsearch(field, b=upper+1)
for i, f in enumerate(field):
print lower <= i <= upper, i == f, i, f
Assuming negative integers are OK:
I think the key is that if you get a value less than your index, you know all indices to the left also do not match their value (since the integers are strictly increasing). Also, once you get an index whose value is greater than the index, everything to the right is incorrect (same reason). You can then do a divide and conquer algorithm like you did in the first case. Something along the lines of:
check middle index:
if equal:
count = count + 1
check both halves, minus this index
elif value > index:
check left side (lower to index)
elif index > value:
check right side (index to upper)
In the worst case (every index matches the value), we still have to check every index.
If the integers are non-negative, then you know even more. You now also know that if an index matches the value, all indices to the left must also match the value (why?). Thus, you get:
check middle index:
if equal:
count = count + indices to the left (index-lower)
check the right side (index to upper)
elif value > index:
check left side (lower to index)
elif index > value:
##Can't happen in this case
Now our worst case is significantly improved. Instead of finding an index that matches and not gaining any new information from it, we gain a ton of information when we find one that matches, and now know half of the indices match.
If "all of the numbers are ints and they appear only once", then you can simply do a binary search for the first pair of numbers where L[i]==i && L[i+1]!=i+1 .
To allow negative ints, check if L[0]<0 , and if so, search between 1..N for:
i>0 && L[i]==i && L[i-1]!=i-1 . Then perform the previous search between i and N.
上一篇: OpenLdap（Centos 5.9）：凭据无效（49）
下一篇: 解决O（logn）中的代码的难题