Finding the first index in which the element and the index are the same

Question

I am to build a python function that takes a sorted list of numbers and outputs the first index the is equal to the element in its place.

It should run on O(log n) which I know how it should be running, operationally, but I can't manage to implement it. I guess I should check if the first element fulfills the required. Then, check whether or not the middle index is bigger than its element or smaller, and then go to the middle index between the previous index and the first\last index(which is a recursive operation.).

My code for now(using @Stefan guidance ):

def Fyn(I,lo,hi):
 while lo < hi:
 if I[(lo+hi)/2]==(lo+hi)/2:
 if I[(lo+hi)/2-1]==(lo+hi)/2-1:
 return Fyn(I,0, (lo+hi)/2)
 else: 
 return (lo+hi)/2
 if I[(lo+hi)/2]<(lo+hi)/2:
 return Fyn(I,(lo+hi)/2,hi)
 else:
 return Fyn(I,lo,(lo+hi)/2)

What remains is actually finding the smallest index for which it happens. Right now it won't always do so. ()

• Pieter B: Make code that keeps using the original list instead of recursive code that splits the list into new lists.
• Meitar Abarbanel: Yes but it has to do the same operation in a really specific way and an unknown number of times which I don't know how to handle without recursion...
• Mike Nakis: Show. Us. Your. Code.
• outis: One suspicious line: some languages can have i == [i], but Python is not one of them. Also, it's not impossible that an algorithm would have an O(n) loop and recursion over the same structure, but it's smelly.
• user8709: The line if i==[i]: isn't looking at the list I at all - [i] is a new list containing that one element. I think you meant if i==I[i]:. BTW - that's an interesting problem - I mistook it for binary search for a bit. I can see that you can recursively eliminate ranges where there's no overlap between the index range and the value range (as indicated by the first/last elements) but I'd like to see the proof that sufficient ranges can be eliminated early to allow an O(log n) solution.

Answer 1

Forget my earlier answer. I actually implemented it now and it works. Not spoiling the whole thing but just answering your question, here's part of my code:

def Fun(I):
 lo, hi = 0, len(I) # We'll search I[lo:hi], i.e., excluding index hi
 while lo < hi:
 check middle index
 adjust lo and hi appropriately
 handle the the result appropriately

Edit: Since Meitar made his final one now, here's mine:

def Fun(I):
 lo, hi = 0, len(I) # We'll search I[lo:hi], i.e., excluding index hi.
 good_index = None # So far we haven't found a good index.
 while lo < hi: # As long as we have a range to look into...
 i = (lo + hi) // 2 # Get an index in the middle.
 if I[i] < i: # If too low here, then earlier ones are, too,
 lo = i + 1 # so we only look at later ones (note the +1 !).
 elif I[i] > i: # If too high here, then later ones are, too,
 hi = i # so we only look at earlier ones.
 else: # If good here, then
 good_index = i # remember this but
 hi = i # keep looking for earlier ones.
 return good_index # Return what we found (real index or None).

Can be tested with this:

import random
try:
 for _ in range(100):
 I = sorted(random.sample(range(-50, 150), 100))
 if Fun(I) != next((i for i, e in enumerate(I) if i == e), None):
 print("wrong answer")
 break
 else:
 print("all correct")
except:
 print("crashed")

• Stefan Pochmann: And please mention in the question that the input is a list of unique integers.
• Meitar Abarbanel: Thank you for answering. How should I adjust lo, hi? By recursion? If so, I would change the list doing that.
• Meitar Abarbanel: That's almost worked. The only problem now is that it has to actually spot the minimal index. What I did is: *check my edit I would really appreciate any guidance or hint.
• Stefan Pochmann: @MeitarAbarbanel How to adjust lo, hi? Like: hi = something.
• Stefan Pochmann: @MeitarAbarbanel Your final answer is still wrong (try for example the input [-1]), but since it's final, I added my solution to my answer now.

Answer 2

Don't slice your list, pass start and end indices instead

def Fun(I):
 def Inner(I, L, R):
 for i in range(L,R):
 if i==[i]:
 return i
 elif I[len(I)/2-1]>len(I)/2-1:
 return Inner(I, L, L + (R/2))
 else:
 return Inner(I, L/2, R)
 return Inner(I, 0, len(I)-1)

• Caleth: This probably doesn't have the right index somewhere, but I am unsure what your requirements are
• Meitar Abarbanel: Thank you for answering. Did you define a function within a function? By the way, there are not initial indication for "L" and "R", how are they achieved?
• Meitar Abarbanel: The function you offer goes through the whole list at the very beginning of its applying, doesn't it?

Answer 3

Here's a starting point - a function that checks whether that constraint can be met somewhere within that range...

def Can_Exist_In_Range (xs, lo, hi) :
 return not ((xs [hi] < lo) || (xs [lo] > hi))

This is using inclusive bounds for convenience, which is actually pretty bad practice in general. If the lowest value is higher than the high index bound, or the highest value is lower than the low index bound, the ranges cannot overlap (assuming the bound indexes are in order, of course).

For divide and conquer, any range that could contain a matching element should be divided into non-overlapping subranges, and each part recursively checked (unless you get a match before checking all of them). Any range that can't contain a matching element, stop subdividing and searching that range.

This isn't binary search. Unless I'm missing something (particularly a rule requring all list elements to be unique integers would be significant), just because the lower-half subrange gets searched doesn't mean you can immediately eliminate the upper-half subrange, which is why I commented that I'm curious about a proof this can be done in O(log n) time. Actually, if you allow non-integer numbers, it's trivial to produce a counter-example that needs O(n) time...

[0.1, 1.1, 2.1, 3.1, 4.1, ...]

Since each element is non-integer, no element can match its index. But since each element is only fractionally higher than its index, there are no non-overlapping ranges to eliminate until you get to the single-element level.

To explain why, even with (potentially non-unique) integers you may need to search both subranges, consider...

 * *
Index: 0 1 2 3 4 5, 6, 7
 [ 1, 2, 2, 4, 5, 6, 6, 8 ]

We have a match in both halves. We want the first one, so no need to search the second half, but we can't know that until after we've searched the first half. Neither subrange can be eliminated until that search is done. After all...

 *
Index: 0 1 2 3 4 5, 6, 7
 [ 1, 2, 3, 4, 5, 6, 6, 8 ]

... when we do the split, we don't know enough to prove that the first subrange contains a match - it might not, in which case the only match we have is the one from the second subrange.

Answer 4

Since you're splitting up the lists, changing the indices, you need to reflect that back into your return calls as the function calls unravel. Something like:

def Fun(I):
 for i in range(0,len(I)-1):
 if i==[i]:
 return i
 elif I[len(I)/2-1]>len(I)/2-1:
 # no need to add if index is below
 return Fun(I[:len(I)/2]) 
 else:
 # if index is greater, add your 'pivot' index
 return ((len(I)/2) - 1) + Fun(I[len(I)/2:]) 

(warning: code untested)

Edit: If you're willing to change your function definition, another way to get your indices to add up which still allows the return of a -1 (or whatever) when the value isn't found.

def Fun(I, base):
 for i in range(0,len(I)-1):
 if i==[i]:
 return i
 elif I[len(I)/2-1]>len(I)/2-1:
 # no need to add if index is below
 return Fun(I[:len(I)/2], base) 
 else:
 # if index is greater, add your 'pivot' index
 return Fun(I[len(I)/2:], (base + len(I)/2 - 1))

(warning again: code untested)

This function also needs code to return when the value is not present (size of list is 1, but the value is not the one you're looking for).

• Meitar Abarbanel: Actually I did consider adding "((len(I)/2) - 1)", but since the list changes, the function might never observe the required element, because it might be out of index to begin with...
• Gabe Noblesmith: If you're willing to change your function definition a little you can pass the index in, which will allow you to always return a -1 (or whatever) when the value isn't found. I will edit my answer.
• Meitar Abarbanel: What I meant is: there could be a proper element, but once you call the function again to another list, the the element might lose the index that made it proper for us.