Introduction

For a plain sorted list, the honest answer is no: you cannot generally test membership in true O(1) time just because the list is sorted. Sorting helps you do O(log n) lookup with binary search. Constant-time membership requires extra structure, special assumptions about the values, or both.

Sorted Order Gives You Binary Search, Not Magic

In a sorted array or list, the usual optimal comparison-based lookup is binary search. Each comparison cuts the remaining search interval roughly in half, which gives O(log n) time.

1def contains(sorted_values: list[int], target: int) -> bool:
2    left = 0
3    right = len(sorted_values) - 1
4
5    while left <= right:
6        mid = (left + right) // 2
7        value = sorted_values[mid]
8
9        if value == target:
10            return True
11        if value < target:
12            left = mid + 1
13        else:
14            right = mid - 1
15
16    return False
17
18
19print(contains([1, 4, 7, 10, 15], 10))
20print(contains([1, 4, 7, 10, 15], 9))

That is already very efficient. If an interviewer asks for O(1) on a sorted list, they are often testing whether you can challenge the premise instead of blindly trying to force the wrong answer.

Why Plain O(1) Membership Is Not Available

An array gives you constant-time access by index, not by value. Knowing that the values are sorted does not tell you where a particular target lives without inspecting the data. In the standard comparison model, you still need enough comparisons to distinguish among many possibilities, which is why binary search is the right baseline.

So the precise answer is:

• sortedness alone does not give arbitrary-value membership in O(1)
• sortedness does give O(log n) membership through binary search

How You Actually Get O(1) Membership

You need preprocessing or a domain restriction.

The common answer is a hash set:

1values = [1, 4, 7, 10, 15]
2lookup = set(values)
3
4print(10 in lookup)
5print(9 in lookup)

Now membership is expected O(1), but the sorted list is no longer doing the work. The hash table is.

Another possibility is a bitset or boolean array when values come from a small known range:

1values = [2, 4, 7]
2present = [False] * 11
3
4for value in values:
5    present[value] = True
6
7print(present[7])
8print(present[5])

That is true constant-time lookup, but only because the value range is bounded and directly indexable.

Special Cases Can Change the Answer

If the list has extra structure, the answer may be different. For example, if you know the list is a continuous arithmetic progression with no gaps, then a small formula can test membership quickly.

1def in_progression(start: int, step: int, length: int, target: int) -> bool:
2    if target < start:
3        return False
4    offset = target - start
5    return offset % step == 0 and offset // step < length
6
7
8print(in_progression(start=3, step=5, length=6, target=18))
9print(in_progression(start=3, step=5, length=6, target=19))

But that is no longer a generic sorted list problem. It is a special mathematical sequence problem.

What Interviewers Usually Want

A strong answer usually sounds like this:

1. For a normal sorted array, the best general lookup is O(log n) with binary search.
2. True O(1) membership requires extra memory, such as a hash set, or a constrained value domain, such as a bitset.
3. There is a space-time tradeoff, and the sorted property is not what enables constant-time membership.

That response shows both algorithm knowledge and the ability to reject an unrealistic assumption cleanly.

Common Pitfalls

• Claiming the sorted order itself somehow enables O(1) lookup.
• Forgetting that expected O(1) hash lookup needs extra memory and preprocessing.
• Ignoring the difference between direct indexing by position and membership by value.
• Missing special-case assumptions such as bounded integers or arithmetic progressions.
• Treating every interview question as if it must have a trick answer instead of stating the real lower-bound idea.

Summary

• A plain sorted list does not support general membership testing in true O(1) time.
• The standard solution is O(log n) binary search.
• Constant-time membership comes from extra structure such as a hash set or bitset.
• Special mathematical patterns can allow formulas, but that is not the generic case.
• In interviews, the best answer is often to explain the tradeoff clearly rather than inventing a false O(1) method.