É sabido que com o módulo timeit é possível mensurar, em Python, o tempo de execução de trechos de códigos. Curioso, fui testar qual é o tempo que leva para se verificar se um determinado número está em um intervalo definido por range, tal como x in range(A, B).

Para o teste, fiz:

$ python -m timeit -s '1000000000 in range(9999999999)'

Ou seja, defini o intervalo [0, 9999999999[, que é gigantesco, e verifiquei se o valor 1000000000 pertence a ele. O resultado obtido foi:

100000000 loops, best of 3: 0.00574 usec per loop

Que, além de resultar em um tempo bastante pequeno, se assemelha, por exemplo, ao tempo de verificar com um intervalo bem menor:

$ python -m timeit -s '1 in range(10)'
100000000 loops, best of 3: 0.00577 usec per loop

Como isso é possível?

De fato, considerando apenas o objeto do tipo range, o tempo para verificar se um determinado valor pertence ao intervalo é, na notação big-O, O(1), que significa que será constante independente do tamanho do espaço verificado, o que explica os tempos de ambos os testes serem iguais. E a explicação para isso é bem simples: matematicamente é muito fácil verificar se um número pertence a um intervalo.

TL;DR

A solução mais básica que consigo imaginar para verificar se um número está em um determinado intervalo é percorrer todos os elementos deste intervalo, comparando um a um com o valor que estou verificando e, se caso encontrar um igual, retornar verdadeiro, caso contrário, falso.

def pertence(sequencia, valor):
    for item in sequencia:
        if item == valor:
            return True
    return False

Com certeza uma solução assim jamais seria O(1), na verdade seria O(n), o que poderia justificar tempos pequenos para intervalos pequenos, mas não justificaria o mesmo para intervalos grandes. Então como é possível?

Matematicamente, podemos dizer que o número x pertence ao intervalo [A, B[ se, e somente se, x for maior ou igual a A e x for menor que B. Isto é:

Toda essa mágica acontece no objeto range graças à implementação do método __contains__, que é implicitamente invocado através do operador in. E, além de verificar se o valor de x é maior ou igual a A e menor a B, quando definido o passo do intervalo, será necessário também verificar se o valor coincide com o passo. Por exemplo, se eu defino o objeto range(0, 10, 2), estarei pegando os valores pares de 0 a 10 e, desta forma, o número 3 não pertencerá ao intervalo, mesmo que seja maior que 0 e menor que 10. Assim, a implementação em Python seria semelhante à:

class range:
    def __contains__(self, x):
        if not self.A <= x < self.B:
            return False
        if self.passo is not None:
            return (x - self.A) % self.passo == 0
        return True

Desta forma, a verificação não depende mais do tamanho do intervalo, mas sim de um número constante de operações, o que caracteriza ser uma solução O(1).

^{Veja funcionando no Repl.it}

Porém, a classe range do Python pertence ao módulo builtins, que é implementada em C, não em Python. Ou seja, embora a lógica seja a mesma, o código que é executado, de fato, para verificar se o valor pertence ao intervalo é outro. A título de curiosidade, é possível acessar o repositório oficial do CPython e verificar a implementação em C, mas especificamente entre as linhas 337 e 379:

static int
range_contains_long(rangeobject *r, PyObject *ob)
{
    int cmp1, cmp2, cmp3;
    PyObject *tmp1 = NULL;
    PyObject *tmp2 = NULL;
    int result = -1;

    /* Check if the value can possibly be in the range. */

    cmp1 = PyObject_RichCompareBool(r->step, _PyLong_Zero, Py_GT);
    if (cmp1 == -1)
        goto end;
    if (cmp1 == 1) { /* positive steps: start <= ob < stop */
        cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
        cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
    }
    else { /* negative steps: stop < ob <= start */
        cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
        cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
    }

    if (cmp2 == -1 || cmp3 == -1) /* TypeError */
        goto end;
    if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
        result = 0;
        goto end;
    }

    /* Check that the stride does not invalidate ob's membership. */
    tmp1 = PyNumber_Subtract(ob, r->start);
    if (tmp1 == NULL)
        goto end;
    tmp2 = PyNumber_Remainder(tmp1, r->step);
    if (tmp2 == NULL)
        goto end;
    /* result = ((int(ob) - start) % step) == 0 */
    result = PyObject_RichCompareBool(tmp2, _PyLong_Zero, Py_EQ);
  end:
    Py_XDECREF(tmp1);
    Py_XDECREF(tmp2);
    return result;
}

O parâmetro r representa o próprio objeto range e o parâmetro ob representa o valor a ser verificado. O objeto r possui os campos start, stop e step que representam o início, final e passo do intervalo. Embora seja uma implementação maior, a lógica é exatamente a apresentada anteriormente em Python.

Na implementação em C, também é possível verificar que o objeto r não é modificado em momento algum, o que implica que o gerador que é definido por range não será modificado ao verificar se o valor pertence ao intervalo. Por ser um gerador e, por definição, gerador poder ser iterado apenas uma vez, seria catastrófico se o operador in percorresse o range, pois o intervalo não teria mais utilidade depois disso. Perceba que estamos tratando aqui apenas do objeto range e suas peculiaridades, o que não implica em ser assim com todos os geradores do Python.

intervalo = range(10)

if 5 in intervalo:
    for i in intervalo:
        print(i)

^{Veja funcionando no Repl.it}