Why is `x in range(10**9)` O(1) for an int but O(n) for a float?

### Two completely different code paths behind one operator `x in r`, where `r` is a `range` object, calls `range.__contains__`. CPython implements that method with a deliberate fork: * If `x` is *exactly* an `int` (or a `bool`, which is an `int` subclass CPython checks for explicitly), the answer is computed with arithmetic and no iteration at all. * For any other object, the operator falls back to the generic sequence search: iterate the range from the beginning, comparing each produced value with `==`, and stop at the first match or at the end. The first path is O(1) — a handful of integer operations regardless of how long the range is. The second is O(n) in the length of the range, and on a long range that is not "a bit slower", it is a hang. ### The arithmetic the fast path does For `x in range(start, stop, step)` with an integer `x`, membership is decidable in closed form. The value must lie inside the half-open interval the range covers, on the correct side of `start` for the sign of `step`, and it must be reachable from `start` by a whole number of steps — that is, `(x - start) % step == 0`. Three comparisons and one remainder, and the answer is known: ```pycon >>> 7 in range(0, 10**18, 7) True >>> 8 in range(0, 10**18, 7) False ``` Both answers come back instantly on a range with 10^17 elements, because nothing is ever produced. ### Why a float cannot take that path The fast path is guarded by an exact type check, not by "is this number-like". A `float`, a `str`, or even a user-defined subclass of `int` all miss it and take the linear scan. Numerically the float answer is often the same — `5.0 == 5` is `True`, so `5.0 in range(10)` is `True` — but the *route* to that answer walked five elements, and on a large range it walks a very long way: ```pycon >>> 9999999.0 in range(10**7) # true, after ~10 million comparisons True >>> 9999999 in range(10**7) # true, immediately True ``` On a typical machine the first line takes on the order of a tenth of a second; the second is microseconds. Push the range to 10^12 and the float form is no longer a slow answer, it is an unfinished one. The same trap catches a value that is *absent*: `5.5 in range(10**7)` must exhaust the whole range before it can say `False`. The int-subclass case is the nastiest version, because the code looks correct. A domain wrapper such as `class RowOffset(int)` reads exactly like an int and compares equal to one, but membership tests against a long range fall off the fast path and quietly become linear. ### Fixing it The fix is one call: normalize the probe to a plain `int` before the test, and be explicit about what "is this an integer" means for your data. ```python def in_progression(x, r): if x != int(x): # a non-integral float is never in a range return False return int(x) in r ``` `int(x)` on a value that is not integral would silently truncate, so the `x != int(x)` guard comes first. For an `int` subclass, `int(x)` returns a plain `int` and restores the fast path. ### The general lesson this question is really testing Containment on a Python sequence is not one algorithm. `in` on a `list` is always a linear scan; `in` on a `set` or `dict` is a hash lookup; `in` on a `str` is a substring search; `in` on a `range` is O(1) for an exact `int` and linear for anything else. The operator hides which one you get, so the cost of `in` is a property of the *container and the probe type together*, never of the syntax. An interviewer asking this usually wants two things: that you know `range.__contains__` is special-cased rather than a scan, and that you know the special case is narrow. The second half is what separates a memorized fact from an understanding you can act on when a membership test in a hot loop turns out to be the bottleneck. ### Version note The arithmetic fast path for integer membership in a `range` has been in CPython since Python 3.2, and the behaviour is unchanged through 3.14. There is no version in which the float form was fast.