Is this efficient? I was under the impression (which is likely inaccurate, because I'm no expert on Python) that range returned a generator or a list outright, making this an O(n) operation.
You're correct. It returns a list from from [a, b), but it's just another example of some expressive (albeit computationally inefficient) notation Python has.
Edit: I take that back. Here's a section from Python's range() documentation:
> The advantage of the range type over a regular list or tuple is that a range object will always take the same (small) amount of memory, no matter the size of the range it represents (as it only stores the start, stop and step values, calculating individual items and subranges as needed).
No, what the docs say is that range is a generator. It never stores the entire list of values, but it does iterate through all the numbers, spitting them out one by one (hence it uses O(1) memory, but O(n) computation).
Equivalent pseudocode:
function in_range(x, a, b):
for i=a; i<b; i++:
if x == i return true
return false
Edit: I take that back. Here's a section from Python's range() documentation:
> The advantage of the range type over a regular list or tuple is that a range object will always take the same (small) amount of memory, no matter the size of the range it represents (as it only stores the start, stop and step values, calculating individual items and subranges as needed).
So it may be a O(1) operation under the hood.