Search і sort: linear, binary, bisect та stability

Linear search — чесний baseline

Послідовний пошук не потребує попереднього порядку і може завершитися на першому match. Worst case відвідує всі n елементів. Він часто правильний для малого одноразового input або predicate, який не має sortable key.

def find_case(rows, case_id):
    for row in rows:
        if row["id"] == case_id:
            return row
    return None

Контракт має сказати, що робити з duplicate IDs: повернути перший, усі, або відхилити input.

Binary search потребує sorted invariant

На кожному кроці порівнюємо target із middle element і лишаємо половину search interval. Для коректності треба чітко визначити half-open межі [lo, hi), termination condition і поведінку на missing target. Якщо дані сортуються перед кожним одиничним lookup, повна ціна включає sort.

bisect: insertion point не дорівнює match

bisect_left повертає позицію, де target можна вставити перед рівними keys зі збереженням порядку. Після цього все одно треба перевірити index < len(data) і equality. Документація окремо попереджає: insort має linear insertion cost, бо переміщення елементів list домінує над logarithmic search.

Python sort: key один раз і stable ties

sorted(iterable, key=...) створює новий list; list.sort() змінює list і повертає None. Key function викликається один раз для кожного record. Stable sort зберігає relative order записів із однаковим key, тому tie policy може спиратися на вхідний порядок лише якщо він сам задокументований і deterministic.

ordered = sorted(
    cases,
    key=lambda row: (row["priority"], row["created_seq"], row["id"]),
)

Explicit tuple key робить business priority видимою. ID як останній tie-breaker прибирає випадковість, якщо input order не є контрактом.

Search/sort QA

• Empty, single, first, middle, last і missing target.
• Duplicate key policy та left/right boundary.
• Already sorted, reverse і partially ordered input.
• Key із None, mixed types або invalid values має explicit validation.
• Input mutation перевіряється окремо.
• Result order порівнюється повністю, не лише як set.

Методичні джерела

• Python Sorting HOWTO
• Python docs — bisect
• Python docs — built-in types

Урок, сценарії, пояснення й вправи створені SEOWORK. Посилання ведуть лише на офіційну документацію та Python Wiki.