Why does `10_000_000 in range(0, 20_000_000, 2)` answer instantly in Python?

### Membership on a container versus membership on a rule For most containers, `x in container` means "look through what is stored". A list has to compare against each element until it finds a match or runs out; a set or dict hashes the value and probes a table. Both are answers about *stored* data. A `range` object stores no values at all — only `start`, `stop` and `step`. That means membership can be answered the way a mathematician would answer it: is this number in the arithmetic progression described by those three integers? ### The two checks For an integer `x`, `range.__contains__` asks: 1. **Is `x` inside the half-open span, in the direction the step points?** With a positive step that means `start <= x < stop`; with a negative step, `stop < x <= start`. 2. **Does `x` land on a step boundary?** That is, is `(x - start)` an exact multiple of `step`? If both hold, the answer is `True`. Neither check depends on the number of values in the range, so the cost is constant no matter how enormous the span is: ```pycon >>> 10_000_000 in range(0, 20_000_000, 2) True >>> 9_999_999 in range(0, 20_000_000, 2) False >>> 999_999_999_996 in range(0, 10**12, 3) True ``` The last one describes a third of a trillion values and still answers immediately. `range.index()` works the same way for an integer argument: it verifies membership, then computes the position as `(x - start) // step` rather than searching for it. So `range(0, 10, 3).index(3)` is `1`, computed rather than found. `count()` is likewise `1` or `0`. ### `bool` gets the fast path too `True` and `False` are instances of `int` in Python, with the values `1` and `0`. `True in range(3)` is therefore `True` via the arithmetic path, not a scan. It is a curiosity rather than something to rely on, but it explains an occasional surprise. ### The trap: non-integers fall back to a scan The optimisation is keyed on the operand's type. If the left-hand value is **not** an int, `range` falls back to the generic sequence membership behaviour: iterate the values and compare each with `==`. That is O(n). ```pycon >>> 1.0 in range(5) True ``` That result is correct — `1.0 == 1` — but it was reached by walking the range from the start, not by arithmetic. On `range(5)` nobody notices. On `range(10**12)` a float that is *not* present makes the interpreter compare a trillion integers, and the call never returns in any useful sense. The same is true of a string, a `Decimal`, or any custom object with an `__eq__`. This is the whole practical lesson of the topic: the constant-time behaviour is real, documented and worth knowing, but it is conditional on the operand being an integer, and nothing in the code makes that condition visible at the call site. A value that arrives from JSON parsing, a CSV column or a division is very often a float without anyone intending it. ### Why not just write a comparison? For a contiguous range, `0 <= x < n` says exactly the same thing as `x in range(n)`, is faster still (no method call, no object), and states the intent without depending on an implementation optimisation. Prefer it in hot code and in code where the operand's type is not guaranteed. `x in range(...)` earns its place where the *step* carries meaning — testing membership of a strided set of positions, for example, where the comparison form would need an explicit modulo and be less readable than the range that produced the offsets in the first place. ### Contrast with a list of the same values `x in [0, 2, 4, ...]` and `x in range(0, n, 2)` produce the same answers and have entirely different costs: the list is a linear scan over materialised objects, the range is two arithmetic operations over three stored integers. Converting a range to a list "so membership works" makes the operation strictly worse in both time and memory. If you find yourself doing that, the range was already the better data structure.