Pylerno
English

Algorithms

Describe an algorithm's behavior and rough growth before optimizing it.

On this page

The concept

An algorithm is a defined sequence of steps that solves a problem. Linear search inspects items one by one and stops at the first match. Its worst-case work grows with the number of items, written O(n). Set membership is typically O(1) on average, but constructing the set also costs time and memory.

Big-O describes growth, not a precise stopwatch result. A straightforward list search may be best for a tiny one-time query; a set may be better for many membership checks. First preserve correctness and clarity, then measure the workload that actually matters.

Worked example

python
def linear_search(items, target):
    for index, item in enumerate(items):
        if item == target:
            return index
    return None


numbers = [7, 3, 9, 2]
position = linear_search(numbers, 9)
if position is not None:
    print("Found at:", position)
print(linear_search(numbers, 100))
unique_numbers = set(numbers)
print(9 in unique_numbers)

Trace the result

  1. linear_search returns the first matching index.
  2. The caller checks is not None because index 0 would also be a valid result.
  3. The final set example answers membership but does not preserve the same index-search contract.
text
Found at: 2
None
True
Line-by-line walkthrough

Lines 1–5: def linear_search(items, target):

Define the function linear_search with input names items, target. Definition stores the operation rather than executing its body. An ordinary call executes a normal function; a coroutine runs when awaited/scheduled, and a generator advances when consumed. Decorators can provide a context-manager or wrapper interface. Indented statements below belong to this operation.

Lines 2–4: for index, item in enumerate(items):

Obtain each item from enumerate(items) and bind it to (index, item) before executing the body. A tuple-shaped target unpacks that item. A loop else, if present, runs only when completion does not use break.

Lines 3–4: if item == target:

Evaluate item == target. Execute the indented body if it is truthy; otherwise follow the alternative branch, if present. Branch order and indentation are part of the behavior.

Line 4: return index

Evaluate index and return that value to the caller. This ends the current function call; subsequent statements on this execution path do not run.

Line 5: return None

Evaluate None and return that value to the caller. This ends the current function call; subsequent statements on this execution path do not run.

Line 8: numbers = [7, 3, 9, 2]

Evaluate [7, 3, 9, 2], then bind or update numbers with the result. The chosen collection determines how later access, membership, and mutation behave. Assignment itself does not imply a deep copy.

Line 9: position = linear_search(numbers, 9)

Evaluate linear_search(numbers, 9), then bind or update position with the result. The call finishes before its return value is bound; a failed call does not produce a successful assignment. Assignment itself does not imply a deep copy.

Lines 10–11: if position is not None:

Evaluate position is not None. Execute the indented body if it is truthy; otherwise follow the alternative branch, if present. Branch order and indentation are part of the behavior.

Line 11: print("Found at:", position)

Evaluate the print arguments from the current state and display them. sep controls separators and end controls the ending when those options are provided. Displaying a value does not return that value from the surrounding function.

Line 12: print(linear_search(numbers, 100))

Evaluate the print arguments from the current state and display them. sep controls separators and end controls the ending when those options are provided. Displaying a value does not return that value from the surrounding function.

Line 13: unique_numbers = set(numbers)

Evaluate set(numbers), then bind or update unique_numbers with the result. The call finishes before its return value is bound; a failed call does not produce a successful assignment. Assignment itself does not imply a deep copy.

Line 14: print(9 in unique_numbers)

Evaluate the print arguments from the current state and display them. sep controls separators and end controls the ending when those options are provided. Displaying a value does not return that value from the surrounding function.

Common mistake

if position incorrectly treats index 0 as absence. Use a distinct sentinel such as None.

Check your understanding

What must hold before binary search on a list?

Choose one answer

Search documentation

Share this page