> ## Documentation Index
> Fetch the complete documentation index at: https://docs.syntblaze.com/llms.txt
> Use this file to discover all available pages before exploring further.
# Python In
The `in` operator is a membership operator that evaluates whether a specified element exists within an iterable, sequence, or collection. It returns a boolean value (`True` if the element is found, `False` otherwise). Its negated counterpart is `not in`.
```python theme={"dark"}
element in collection
element not in collection
```
## Underlying Implementation
When the Python interpreter encounters the `in` operator, it delegates the evaluation to the collection's data model. Specifically, the expression `x in y` translates to a call to the `__contains__()` dunder (magic) method of the collection `y`.
```python theme={"dark"}
# The standard expression:
x in y
# Is internally evaluated as:
type(y).__contains__(y, x)
```
## Fallback Protocol
If the target object does not implement the `__contains__()` method, Python does not immediately fail. Instead, it falls back to iteration protocols in the following order:
1. **`__iter__()`**: Python attempts to iterate over the object, checking each item for *identity* first, and then *equality* (equivalent to `x is item or x == item`). It short-circuits and returns `True` upon the first match. This identity-first check is a critical semantic detail. For example, using a custom generator that lacks a `__contains__` method demonstrates how identity supersedes equality:
```python theme={"dark"}
x = float('nan')
def custom_iterable():
yield x
# Evaluates to True because 'x is x',
# even though 'float('nan') == float('nan')' is False.
x in custom_iterable()
```
2. **`__getitem__()`**: If the object does not implement `__iter__()` but implements sequence semantics, Python attempts to access elements using sequential integer indices starting from `0` until a match is found or an `IndexError` is raised.
3. **`TypeError`**: If none of these methods are implemented, Python raises a `TypeError`, indicating the right-hand operand is not iterable.
## Algorithmic Complexity
The time complexity of the `in` operator is strictly dependent on the underlying data structure of the collection being queried:
* **Sets and Dictionaries (`set`, `dict`):** Average case **O(1)**, worst case **O(n)**. The `in` operator computes the hash of the target element and checks the corresponding bucket in the hash table. Note that for dictionaries, `in` evaluates membership against the *keys*, not the values.
* **Lists and Tuples (`list`, `tuple`):** **O(n)**. Python performs a linear scan, evaluating identity and then equality (`x is item or x == item`) for each element sequentially until a match is found or the sequence is exhausted.
* **Strings (`str`):** Average case **O(n)**, worst case **O(n \* m)** (where *n* is the length of the main string and *m* is the length of the substring). Unlike other sequences where `in` checks for exact element matches, applying `in` to strings invokes a substring search algorithm (typically a variation of Boyer-Moore-Horspool in CPython).
Tired of Poor Python Skills? Fix That With Deep Grasping!
Learn More
