Trovare il primo indice in cui l'elemento e l'indice sono gli stessi

Dimentica la mia risposta precedente. L'ho effettivamente implementato ora e funziona. Non rovinare tutto ma semplicemente rispondendo alla tua domanda, ecco parte del mio codice:

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

Modifica: Da quando Meitar ha realizzato il suo ultimo album, ecco il mio:

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

Può essere testato con questo:

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")

Non tagliare l'elenco, passa invece gli indici di inizio e fine

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)

Ecco un punto di partenza: una funzione che controlla se il vincolo può essere soddisfatto da qualche parte all'interno di quell'intervallo ...

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

Questo sta usando limiti compresi per comodità, che in realtà è una pratica piuttosto cattiva in generale. Se il valore più basso è superiore al limite superiore dell'indice, oppure il valore più alto è inferiore al limite inferiore dell'indice, gli intervalli non possono sovrapporsi (presupponendo che gli indici associati siano in ordine, ovviamente).

Per dividere e conquistare, qualsiasi intervallo che potrebbe contenere un elemento corrispondente dovrebbe essere diviso in sottogruppi non sovrapposti e ogni parte ricorsivamente controllata (a meno che non si ottenga una corrispondenza prima di controllarli tutti). Qualsiasi intervallo che non può contenere un elemento corrispondente, smettere di suddividere e cercare tale intervallo.

Questa non è una ricerca binaria. A meno che non mi manchi qualcosa (in particolare una regola che renda significativi tutti gli elementi della lista come interi unici sarebbe significativa), solo perché il sub-intervallo inferiore viene cercato non significa che puoi immediatamente eliminare il sotto-intervallo superiore, che è il motivo per cui ho commentato che sono curioso di provare che questo può essere fatto in tempo O (log n). In realtà, se permetti numeri non interi, è banale produrre un contro-esempio che ha bisogno del tempo O (n) ...

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

Poiché ogni elemento non è intero, nessun elemento può corrispondere al suo indice. Ma dal momento che ogni elemento è solo leggermente più alto del suo indice, non ci sono intervalli non sovrapposti da eliminare fino ad arrivare al livello di un singolo elemento.

Per spiegare perché, anche con interi (potenzialmente non univoci) potresti aver bisogno di cercare entrambi i sottogruppi, considera ...

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

Abbiamo una partita in entrambi i tempi. Vogliamo il primo, quindi non c'è bisogno di cercare la seconda metà, ma non possiamo sapere che fino a dopo abbiamo cercato il primo semestre. Nessuno dei due subrange può essere eliminato fino a quando la ricerca non viene completata. Dopo tutto ...

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

... quando facciamo lo split, non ne sappiamo abbastanza per dimostrare che il primo subrange contiene una corrispondenza - potrebbe non esserlo, nel qual caso l'unica corrispondenza che abbiamo è quella del secondo subrange.

Dato che stai dividendo gli elenchi, modificando gli indici, devi rispecchiarli nelle tue chiamate di ritorno quando le chiamate di funzione si distruggono. Qualcosa come:

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:]) 

(avviso: codice non testato)

Modifica: se sei disposto a modificare la definizione della tua funzione, un altro modo per ottenere gli indici da sommare che consente comunque il ritorno di un -1 (o di qualsiasi altra cosa) quando il valore non viene trovato.

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))

(avviso di nuovo: codice non testato)

Questa funzione ha bisogno anche del codice da restituire quando il valore non è presente (la dimensione della lista è 1, ma il valore non è quello che stai cercando).