Learn algorithms and data structures through lookup tasks

An order-ID list contains duplicates. To check whether a new ID already exists, you can scan the list, build a set, or sort the data and use binary search. Each method distributes work differently between preparation, lookup, and updates. They also preserve different information.

Define the task before choosing a structure: the input is a collection of string IDs, a query returns only whether an ID exists, duplicates are allowed in the original data, and queries do not modify the data. These conditions make the methods comparable. If the task changes to displaying every order in submission order or counting occurrences, the representation needs to change too.

Complexity describes growth with input size

Let the list contain n elements. A sequential scan can stop when it finds a match, but looking for an absent value requires checking every element. Its worst-case time complexity is O(n). This model treats a string comparison as one operation. If string lengths also grow with input size, include the cost of comparing them.

Checking n new IDs by scanning another list of comparable size can require O(n²) work. This describes a growth relationship, not a fixed duration. Caches, allocation, string length, implementation, and hardware affect measured time. For small inputs, a simple scan may already satisfy the requirement. Complexity notation cannot tell you how many milliseconds it will take.

State what a space estimate includes. A scan needs only a few temporary variables, so its additional space is O(1). The original list still consumes memory. Constant additional space does not mean the entire program uses constant memory.

Why sets suit membership checks

Python's set stores unique elements. It uses a hash value to locate candidate positions and equality checks to identify the element. A hash collision means distinct elements may have the same hash value. The set handles collisions; they do not mean two different order IDs become the same order.

Set membership is commonly described as average O(1). This is a conditional estimate, not a promise of constant time for every input. Hashing, comparisons, resizing, and collision handling cost work. Lookup can degrade in the worst case. Elements must also be hashable; mutable containers such as lists cannot be used directly as set elements.

A set discards occurrence counts and does not promise to preserve the input's insertion order. Use a dictionary of counts or collections.Counter when counts matter. If you need both order and deduplication, specify whether you preserve the first occurrence or sort by ID. Python dictionaries preserve insertion order. Do not describe sets and dictionaries as having identical ordering behavior.

What binary search assumes

Binary search repeatedly narrows a range in a sorted sequence and needs O(log n) comparisons to locate a position. bisect_left returns an insertion position under the sequence's ordering. It does not return a Boolean saying that the target exists. The position may be at the end or point to a larger value. Check both the bounds and equality.

Preparing a sorted list has a cost, commonly estimated as O(n log n). With stable data and many queries, that cost can be spread across queries. For one lookup, sorting may do more work than a scan. If you sort again for every query, the complete operation is not O(log n).

Python lists are dynamically sized array-like containers. Inserting in the middle can require moving later elements, which is still O(n) work. Binary search finds the insertion position more quickly; it does not remove the movement cost. When frequent updates, ordered iteration, and range queries are all required, assess trees or database indexes along with their storage and maintenance costs.

Check all three methods on the same data

The example builds a set from duplicate IDs and then creates a sorted list of unique IDs. The has function performs binary search on that prepared snapshot. The checks include an existing ID, O-1, and an absent ID beyond the final element, O-4. The latter exercises the bounds check.

from bisect import bisect_left
ids = ["O-3", "O-1", "O-3", "O-2"]
ordered = sorted(set(ids))
known = set(ids)
def has(value):
    position = bisect_left(ordered, value)
    return position < len(ordered) and ordered[position] == value
for value in ["O-1", "O-4"]:
    assert (value in ids) == (value in known) == has(value)
assert len(known) == 3
print(ordered, has("O-4"))

The output is ['O-1', 'O-2', 'O-3'] False. The set contains three elements while the input list contains four, showing that duplicate counts have been lost. The queries agree about membership for these test values. They do not preserve identical information about the data.

This is an offline behavior check, without a benchmark or an order database. If several requests create orders concurrently, checking for absence and then inserting can still race. Database uniqueness constraints, transactions, and request idempotency must help enforce the business rule. A process-local set cannot guarantee consistency across every service instance.

Choose structures using required operations

List the frequent operations and their constraints first. A scan is easy to implement and inspect when membership queries are few. Assess a set for repeated queries that do not need ordering. Use a mapping when you need counts or records associated with IDs. A queue expresses ordered task processing more directly than an unordered set.

The choice of queue container matters too. Removing the first item from a Python list shifts later elements. collections.deque suits frequent additions and removals at both ends. A stack follows last-in, first-out behavior; a graph's adjacency list represents edges between nodes. These structures solve different problems and do not belong in one universal performance ranking.

For changing data, specify how derived indexes stay synchronized. Updating the original list without updating known or ordered leaves queries using an older snapshot. Multiple representations of the same business data increase maintenance costs and opportunities for errors. Avoid letting callers independently modify values that can be derived from one authoritative source.

Exercise: add counts and updates

Turn the example into a module with membership lookup, occurrence-count lookup, and ID insertion. Keep the original list as the authoritative data. Define how initialization and insertion update the auxiliary structures. Adding an existing ID still changes its count, even if membership remains unchanged.

Test an empty list, a single element, repeated values, targets below the minimum, targets between existing values, targets above the maximum, and queries before and after insertion. Membership must agree with a direct scan. Counts must agree with counts in the original list. The sorted auxiliary list must remain sorted.

Record preparation, lookup, and insertion costs separately. For performance conclusions, measure a stated data size, string length, query mix, and runtime environment. Separate preparation time from lookup time. Passing assertions in this small example establishes behavior for those inputs; it does not establish a general benchmark result.