Dificulty decisive code in O (logn)

Question

I wrote a function that enters a list of unique ints as a list in order (from small to large). Im should find in the list the index that matches the value in the index. for example, if L [2] == 2, the conclusion is true. therefore, after I did this in O (logn) complexity, now I want to find how many indexes behave like in the specified list with the same O (logn) complexity. I upload my first code that executes the first part, and the second code that I need for help:

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 

Answer 1

This is not possible with the restrictions you specified. The best difficulty you can theoretically achieve is O (n).

O () accepts the worst case (just a definition, you can refuse this part). And in the worst case, you will always have to look at each element to check that it is equal to its index.

The case changes if you have more restrictions (for example, numbers are all int and none can appear more than once, i.e. there are no two consecutive numbers). Maybe this is so?

EDIT:

Having heard that my alleged limitations are actually applied (for example, only once), I propose this approach: we can safely assume that you can have only one continuous range, where all your relevant records are located. I. e. you only need to find the lower bound and the upper bound. Then the desired result will be the size of this range.

Each boundary can be safely found using binary search, each of which 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 

I used this 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 

Answer 2

Assuming negative integers in order:

I think the key is that if you get a value less than your index, you know that all the indices on the left also don't match their value (since integers are strictly increasing). In addition, as soon as you get an index whose value is greater than the index, everything on the right is wrong (for the same reason). Then you can perform the separation and subjugation algorithm, as in the first case. Something like:

 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 (each index corresponds to a value), we still have to check each index.

If integers are non-negative, then you know even more. Now you also know that if the index matches the value, all the indexes on the left should also match the value (why?). So 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 has improved significantly. Instead of finding an index that matches and does not receive any new information, we get a lot of information when we find one that matches, and now we know that half of the indexes match.

Answer 3

If "all numbers are int and they appear only once", you can simply perform a binary search for the first pair of numbers, where L[i]==i && L[i+1]!=i+1 .

To resolve negative ints, check if L[0]<0 , and if so, find between 1..N for:
i>0 && L[i]==i && L[i-1]!=i-1 . Then do the previous search between i and N.