8 эффективных алгоритмов поиска и сортировки на Python: примеры

Для кого эта статья:

• начинающие и опытные программисты, стремящиеся улучшить свои навыки в программировании на Python
• студенты и соискатели, подготавливающиеся к техническим собеседованиям

• разработчики, ищущие способы оптимизации своих алгоритмов и решения задач с использованием эффективных методов поиска и сортировки

  Алгоритмы поиска и сортировки — краеугольный камень эффективного программирования. Овладение этими алгоритмами на Python откроет двери к оптимизации кода и прохождению технических собеседований. В этой статье мы препарируем 8 фундаментальных алгоритмов, разберём их по косточкам с примерами кода, сравним их эффективность и рассмотрим практические сценарии применения. От классической пузырьковой сортировки до изощрённых методов быстрого поиска — ваш арсенал программиста станет неоспоримо мощнее. 🚀

Хотите не просто понимать алгоритмы, а применять их в реальных проектах? Курс Обучение Python-разработке от Skypro погружает вас в мир эффективного кодирования, где алгоритмы поиска и сортировки — лишь фундамент. Под руководством практикующих экспертов вы научитесь создавать высокопроизводительные приложения, оптимизировать сложные системы и писать код, востребованный на рынке труда. Инвестируйте в навыки, которые действительно ценят работодатели! 💼

Основы алгоритмов поиска и сортировки в Python

Алгоритмы поиска и сортировки — неотъемлемые компоненты компьютерных наук, позволяющие эффективно управлять данными. Python, благодаря своему выразительному синтаксису, делает реализацию этих алгоритмов интуитивно понятной даже для начинающих программистов.

Сортировка данных — это процесс упорядочивания элементов в определённой последовательности. В Python встроенная функция sorted() и метод .sort() используют алгоритм Timsort — гибрид сортировки слиянием и вставками. Однако понимание базовых алгоритмов критически важно для разработчика.

Алгоритмы поиска, с другой стороны, позволяют находить конкретные элементы в наборе данных. Выбор правильного алгоритма зависит от структуры данных и конкретной задачи.

Алексей Мартынов, старший преподаватель алгоритмов и структур данных

Однажды на собеседовании мой студент столкнулся с, казалось бы, простой задачей: найти два числа в массиве, сумма которых равна заданному значению. Он начал писать вложенные циклы с временной сложностью O(n²), но интервьюер намекнул, что можно лучше. Студент вспомнил наши занятия по алгоритмам поиска и предложил решение с хеш-таблицей за O(n). Интервьюер был впечатлён! Но самое интересное произошло, когда задачу усложнили, попросив найти два числа с минимальной разницей. Тут пригодилась сортировка с последующим линейным проходом — O(n log n). Именно глубокое понимание алгоритмов, а не просто знание синтаксиса Python, выделило моего студента среди других кандидатов.

При оценке эффективности алгоритмов используют понятия временной и пространственной сложности, обычно выражаемые в нотации "O большое". Эта нотация описывает верхнюю границу роста времени выполнения или потребления памяти относительно размера входных данных.

Ключевые факторы, влияющие на выбор алгоритма:

• Размер и тип данных (числа, строки, объекты)
• Требуемая стабильность сортировки (сохранение порядка эквивалентных элементов)
• Доступная память
• Изначальная упорядоченность данных
• Требования к скорости выполнения

Понимание этих основ позволит вам осознанно выбирать оптимальные алгоритмы для решения конкретных задач программирования на Python. 🧠

Алгоритмы сортировки: от пузырьковой до быстрой

Рассмотрим четыре фундаментальных алгоритма сортировки, от простейших до более сложных, но эффективных. Каждый из них имеет свои особенности, преимущества и недостатки.

Пузырьковая сортировка (Bubble Sort)

Пузырьковая сортировка — элементарный алгоритм, основанный на многократном "всплытии" более легких элементов к вершине списка, подобно пузырькам воздуха в воде.

def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Флаг для оптимизации
swapped = False
for j in range(0, n – i – 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# Если не было обменов, массив отсортирован
if not swapped:
break
return arr

# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(numbers)) # [11, 12, 22, 25, 34, 64, 90]

Временная сложность: O(n²) в худшем и среднем случаях, O(n) в лучшем случае (для уже отсортированного массива с оптимизацией).

Сортировка вставками (Insertion Sort)

Сортировка вставками работает аналогично тому, как мы сортируем игральные карты в руке: берем новую карту и вставляем ее в правильное место среди уже отсортированных.

def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i – 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr

# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
print(insertion_sort(numbers)) # [11, 12, 22, 25, 34, 64, 90]

Временная сложность: O(n²) в худшем и среднем случаях, O(n) в лучшем случае (для почти отсортированных данных).

Сортировка слиянием (Merge Sort)

Сортировка слиянием использует подход "разделяй и властвуй": разбивает список на подсписки, сортирует их, а затем объединяет.

def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]

# Рекурсивная сортировка подмассивов
merge_sort(left)
merge_sort(right)

i = j = k = 0

# Слияние подмассивов
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1

# Проверка оставшихся элементов
while i < len(left):
arr[k] = left[i]
i += 1
k += 1

while j < len(right):
arr[k] = right[j]
j += 1
k += 1

return arr

# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(numbers)) # [11, 12, 22, 25, 34, 64, 90]

Временная сложность: O(n log n) во всех случаях, что делает ее более эффективной для больших массивов по сравнению с пузырьковой и сортировкой вставками.

Быстрая сортировка (Quick Sort)

Быстрая сортировка — еще один алгоритм типа "разделяй и властвуй", который выбирает опорный элемент и разделяет массив на элементы меньше и больше опорного.

def quick_sort(arr):
if len(arr) <= 1:
return arr

pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]

return quick_sort(left) + middle + quick_sort(right)

# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
print(quick_sort(numbers)) # [11, 12, 22, 25, 34, 64, 90]

Временная сложность: O(n log n) в среднем и лучшем случаях, O(n²) в худшем случае (при неудачном выборе опорного элемента).

В практических задачах Python-разработки выбор алгоритма сортировки должен основываться на характеристиках данных и требованиях к производительности. Для большинства случаев встроенная функция sorted() или метод .sort() будут оптимальным выбором, так как они реализуют гибридный алгоритм Timsort. 🔍

Линейный и бинарный поиск: реализация на Python

Алгоритмы поиска — второй важный компонент работы с данными. Рассмотрим два фундаментальных алгоритма: линейный и бинарный поиск, а также их реализацию на Python.

Линейный поиск — простейший алгоритм, проверяющий каждый элемент последовательно, пока не найдет искомый или не достигнет конца списка.

Линейный поиск (Linear Search)

Линейный поиск — наиболее интуитивный алгоритм поиска, последовательно проверяющий каждый элемент массива.

def linear_search(arr, target):
for i, item in enumerate(arr):
if item == target:
return i # Возвращает индекс найденного элемента
return -1 # Возвращает -1, если элемент не найден

# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
target = 22
result = linear_search(numbers, target)
print(f"Элемент {target} найден на позиции {result}" if result != -1 else f"Элемент {target} не найден")

Временная сложность: O(n) — в худшем случае придется проверить все n элементов.

Преимущества линейного поиска:

• Работает с неотсортированными массивами
• Прост в реализации
• Эффективен для маленьких массивов
• Не требует дополнительной памяти

Недостатки:

• Неэффективен для больших массивов
• Линейная временная сложность

Бинарный поиск (Binary Search)

Бинарный поиск использует подход "разделяй и властвуй", многократно деля отсортированный массив пополам и сужая область поиска.

def binary_search(arr, target):
left = 0
right = len(arr) – 1

while left <= right:
mid = (left + right) // 2

# Если элемент найден
if arr[mid] == target:
return mid

# Если элемент меньше среднего, ищем в левой половине
elif arr[mid] > target:
right = mid – 1

# Если элемент больше среднего, ищем в правой половине
else:
left = mid + 1

return -1 # Элемент не найден

# Пример использования
sorted_numbers = [11, 12, 22, 25, 34, 64, 90]
target = 25
result = binary_search(sorted_numbers, target)
print(f"Элемент {target} найден на позиции {result}" if result != -1 else f"Элемент {target} не найден")

Рекурсивная реализация бинарного поиска:

def binary_search_recursive(arr, target, left=0, right=None):
if right is None:
right = len(arr) – 1

# Базовый случай: элемент не найден
if left > right:
return -1

mid = (left + right) // 2

# Если элемент найден
if arr[mid] == target:
return mid

# Рекурсивный случай: ищем в левой половине
elif arr[mid] > target:
return binary_search_recursive(arr, target, left, mid – 1)

# Рекурсивный случай: ищем в правой половине
else:
return binary_search_recursive(arr, target, mid + 1, right)

# Пример использования
sorted_numbers = [11, 12, 22, 25, 34, 64, 90]
target = 64
result = binary_search_recursive(sorted_numbers, target)
print(f"Элемент {target} найден на позиции {result}" if result != -1 else f"Элемент {target} не найден")

Временная сложность: O(log n) — каждая итерация уменьшает размер области поиска вдвое.

Преимущества бинарного поиска:

• Очень эффективен для больших массивов данных
• Логарифмическая временная сложность
• Минимальное количество сравнений

Недостатки:

• Работает только с отсортированными массивами
• Требует произвольного доступа к элементам (не подходит для связных списков)
• Сложнее реализовать корректно (особенно рекурсивную версию)

Михаил Соколов, специалист по алгоритмической оптимизации

Недавно мы работали над оптимизацией поискового микросервиса, который обрабатывал запросы к базе данных товаров крупного интернет-магазина. Первоначальная реализация использовала простой линейный поиск, что приводило к заметным задержкам при работе с каталогом из 500,000+ позиций. Система тратила до 2 секунд на каждый поисковый запрос. Внедрив индексирование и бинарный поиск, мы сократили время отклика до 50 миллисекунд — в 40 раз быстрее! Но самое интересное произошло, когда нам пришлось обрабатывать запросы с опечатками: бинарный поиск оказался бесполезен. Мы внедрили алгоритмы нечёткого поиска на базе расстояния Левенштейна, комбинируя их с бинарным для предварительной фильтрации. Этот случай отлично демонстрирует, что нет универсального алгоритма — выбор зависит от конкретной задачи и характера данных.

При работе с Python стоит помнить, что стандартная библиотека содержит модуль bisect, который предоставляет оптимизированные функции для работы с отсортированными списками, включая бинарный поиск:

import bisect

def binary_search_with_bisect(arr, target):
i = bisect.bisect_left(arr, target)
if i != len(arr) and arr[i] == target:
return i
return -1

# Пример использования
sorted_numbers = [11, 12, 22, 25, 34, 64, 90]
target = 34
result = binary_search_with_bisect(sorted_numbers, target)
print(f"Элемент {target} найден на позиции {result}" if result != -1 else f"Элемент {target} не найден")

Выбор между линейным и бинарным поиском зависит от конкретной задачи. Линейный поиск подходит для неотсортированных или маленьких массивов, а бинарный — для больших отсортированных наборов данных, где критична производительность. 🔍

Продвинутые алгоритмы сортировки для сложных задач

Для решения более сложных задач сортировки и поиска в Python доступны продвинутые алгоритмы, которые предлагают повышенную эффективность в определенных сценариях. Рассмотрим четыре таких алгоритма: сортировку подсчётом, сортировку кучей, поразрядную сортировку и сортировку Шелла.

Сортировка подсчётом (Counting Sort)

Сортировка подсчётом — неклассический алгоритм сортировки, который работает, подсчитывая количество вхождений каждого уникального элемента в массиве. Идеально подходит для массивов с небольшим диапазоном значений.

def counting_sort(arr):
# Находим максимальное значение для создания массива подсчёта
max_value = max(arr)
min_value = min(arr)
range_of_values = max_value – min_value + 1

# Создаем массив подсчёта
count = [0] * range_of_values

# Подсчитываем количество каждого элемента
for num in arr:
count[num – min_value] += 1

# Восстанавливаем отсортированный массив
sorted_array = []
for i in range(range_of_values):
sorted_array.extend([i + min_value] * count[i])

return sorted_array

# Пример использования
numbers = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(numbers)) # [1, 2, 2, 3, 3, 4, 8]

Временная сложность: O(n + k), где n — количество элементов, а k — диапазон значений. Пространственная сложность: O(k).

Сортировка кучей (Heap Sort)

Сортировка кучей использует структуру данных "двоичная куча" для построения отсортированного массива. Python предоставляет модуль heapq для работы с кучами.

def heap_sort(arr):
import heapq

# Преобразуем исходный массив в кучу
heap = arr.copy()
heapq.heapify(heap)

# Извлекаем элементы из кучи в отсортированном порядке
sorted_array = []
while heap:
sorted_array.append(heapq.heappop(heap))

return sorted_array

# Пример использования
numbers = [12, 11, 13, 5, 6, 7]
print(heap_sort(numbers)) # [5, 6, 7, 11, 12, 13]

Также можно реализовать сортировку кучей без использования встроенного модуля:

def heapify(arr, n, i):
largest = i # Инициализируем наибольший элемент как корень
left = 2 * i + 1
right = 2 * i + 2

# Проверяем, больше ли левый дочерний элемент корня
if left < n and arr[left] > arr[largest]:
largest = left

# Проверяем, больше ли правый дочерний элемент корня
if right < n and arr[right] > arr[largest]:
largest = right

# Если наибольший элемент не корень
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # Обмен

# Рекурсивно приводим к свойствам кучи поддерево
heapify(arr, n, largest)

def heap_sort_manual(arr):
n = len(arr)

# Построение max-heap
for i in range(n // 2 – 1, -1, -1):
heapify(arr, n, i)

# Извлечение элементов из кучи
for i in range(n – 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # Обмен
heapify(arr, i, 0)

return arr

# Пример использования
numbers = [12, 11, 13, 5, 6, 7]
print(heap_sort_manual(numbers)) # [5, 6, 7, 11, 12, 13]

Временная сложность: O(n log n) во всех случаях. Пространственная сложность: O(1).

Поразрядная сортировка (Radix Sort)

Поразрядная сортировка — нестандартный алгоритм сортировки, который работает с числами, сортируя их по разрядам (от младшего к старшему или наоборот).

def radix_sort(arr):
# Находим максимальное число для определения количества цифр
max_num = max(arr)

# Выполняем сортировку подсчетом для каждого разряда
exp = 1
while max_num // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10

return arr

def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10

# Подсчитываем количество каждой цифры
for i in range(n):
digit = (arr[i] // exp) % 10
count[digit] += 1

# Накапливаем суммы для определения позиций
for i in range(1, 10):
count[i] += count[i – 1]

# Создаем отсортированный по текущему разряду массив
for i in range(n – 1, -1, -1):
digit = (arr[i] // exp) % 10
output[count[digit] – 1] = arr[i]
count[digit] -= 1

# Копируем отсортированный массив обратно в исходный
for i in range(n):
arr[i] = output[i]

# Пример использования
numbers = [170, 45, 75, 90, 802, 24, 2, 66]
print(radix_sort(numbers)) # [2, 24, 45, 66, 75, 90, 170, 802]

Временная сложность: O(d * (n + k)), где d — количество цифр в наибольшем числе, n — количество элементов, k — диапазон значений цифр (обычно 10). Пространственная сложность: O(n + k).

Сортировка Шелла (Shell Sort)

Сортировка Шелла — улучшенная версия сортировки вставками, которая позволяет далеко отстоящим элементам меняться местами раньше, чем близким.

def shell_sort(arr):
n = len(arr)
# Начинаем с большого промежутка, затем уменьшаем его
gap = n // 2

while gap > 0:
# Выполняем сортировку вставками с текущим промежутком
for i in range(gap, n):
temp = arr[i]
j = i

# Сдвигаем элементы, которые больше temp и находятся на gap позиций левее
while j >= gap and arr[j – gap] > temp:
arr[j] = arr[j – gap]
j -= gap

arr[j] = temp

gap //= 2

return arr

# Пример использования
numbers = [12, 34, 54, 2, 3]
print(shell_sort(numbers)) # [2, 3, 12, 34, 54]

Временная сложность: зависит от выбранной последовательности промежутков, но обычно находится между O(n log n) и O(n²). Пространственная сложность: O(1).

Сравнительная таблица продвинутых алгоритмов сортировки:

Выбор продвинутого алгоритма сортировки зависит от специфики задачи:

• Сортировка подсчётом — для небольших диапазонов целочисленных значений
• Сортировка кучей — для задач с ограниченной памятью и требованием гарантированной производительности
• Поразрядная сортировка — для чисел с большим количеством разрядов или строк одинаковой длины
• Сортировка Шелла — как универсальное решение с хорошей производительностью на практике

Эти алгоритмы расширяют арсенал Python-разработчика для решения нестандартных задач сортировки и поиска, позволяя выбирать оптимальный инструмент для конкретного сценария. 🔧

Практическое применение алгоритмов: решение задач

Знание алгоритмов поиска и сортировки в Python имеет прямое практическое применение при решении реальных задач. Рассмотрим несколько типичных сценариев, где эти алгоритмы демонстрируют свою эффективность.

Задача 1: Поиск двух чисел с заданной суммой

Требуется найти в массиве два числа, сумма которых равна заданному значению.

def find_two_sum_naive(nums, target):
# Наивное решение с вложенными циклами – O(n²)
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return None

def find_two_sum_optimized(nums, target):
# Оптимизированное решение с хеш-таблицей – O(n)
num_map = {} # Значение -> индекс
for i, num in enumerate(nums):
complement = target – num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i
return None

# Пример использования
nums = [2, 7, 11, 15]
target = 9
print(find_two_sum_naive(nums, target)) # [0, 1]
print(find_two_sum_optimized(nums, target)) # [0, 1]

Оптимизированное решение демонстрирует, как использование хеш-таблицы (словаря в Python) может значительно ускорить поиск, сократив временную сложность с O(n²) до O(n).

Задача 2: Поиск k наименьших элементов

Необходимо найти k наименьших элементов в неотсортированном массиве.

def find_k_smallest_sort(nums, k):
# Решение с использованием сортировки – O(n log n)
return sorted(nums)[:k]

def find_k_smallest_heap(nums, k):
# Решение с использованием кучи – O(n log k)
import heapq
return heapq.nsmallest(k, nums)

def find_k_smallest_quickselect(nums, k):
# Решение с использованием алгоритма быстрого выбора – O(n) в среднем
if not nums or k <= 0 or k > len(nums):
return []

# Внутренняя функция для быстрого выбора
def quickselect(left, right, k_smallest):
if left == right:
return nums[left]

# Выбираем опорный элемент и разделяем массив
pivot_index = partition(left, right)

# Проверяем, является ли опорный элемент k-м наименьшим
if pivot_index == k_smallest:
return nums[pivot_index]
# Если опорный элемент больше, ищем в левой части
elif pivot_index > k_smallest:
return quickselect(left, pivot_index – 1, k_smallest)
# Иначе, ищем в правой части
else:
return quickselect(pivot_index + 1, right, k_smallest)

# Функция разделения массива вокруг опорного элемента
def partition(left, right):
pivot = nums[right]
i = left
for j in range(left, right):
if nums[j] <= pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[right] = nums[right], nums[i]
return i

# Находим k-й наименьший элемент
quickselect(0, len(nums) – 1, k – 1)
# Возвращаем k наименьших элементов
return sorted(nums[:k])

# Пример использования
nums = [7, 10, 4, 3, 20, 15]
k = 3
print(find_k_smallest_sort(nums, k)) # [3, 4, 7]
print(find_k_smallest_heap(nums, k)) # [3, 4, 7]
print(find_k_smallest_quickselect(nums, k)) # [3, 4, 7]

Эта задача демонстрирует разные подходы: сортировка всего массива (избыточно для больших n), использование кучи (эффективно для больших n и малых k) и алгоритм быстрого выбора (оптимален в среднем случае).

Задача 3: Объединение отсортированных массивов

Требуется объединить два отсортированных массива в один отсортированный массив.

def merge_sorted_arrays_simple(arr1, arr2):
# Простое решение с использованием встроенной сортировки – O((n+m) log(n+m))
return sorted(arr1 + arr2)

def merge_sorted_arrays_efficient(arr1, arr2):
# Эффективное решение с использованием алгоритма слияния – O(n+m)
result = []
i = j = 0

# Сравниваем элементы из обоих массивов и добавляем меньший
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1

# Добавляем оставшиеся элементы
result.extend(arr1[i:])
result.extend(arr2[j:])

return result

# Пример использования
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
print(merge_sorted_arrays_simple(arr1, arr2)) # [1, 2, 3, 4, 5, 6, 7, 8]
print(merge_sorted_arrays_efficient(arr1, arr2)) # [1, 2, 3, 4, 5, 6, 7, 8]

Эффективное решение использует принцип сортировки слиянием и демонстрирует, как можно достичь линейной временной сложности O(n+m) вместо O((n+m) log(n+m)) при использовании встроенной сортировки.

Задача 4: Поиск медианы двух отсортированных массивов

Требуется найти медиану двух отсортированных массивов.

def find_median_naive(nums1, nums2):
# Наивное решение с объединением и сортировкой – O((n+m) log(n+m))
merged = sorted(nums1 + nums2)
n = len(merged)
if n % 2 == 1:
return merged[n // 2]
else:
return (merged[n // 2 – 1] + merged[n // 2]) / 2

def find_median_efficient(nums1, nums2):
# Эффективное решение с бинарным поиском – O(log(min(n,m)))
# Убеждаемся, что nums1 не длиннее nums2
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1

x, y = len(nums1), len(nums2)
low, high = 0, x

while low <= high:
partitionX = (low + high) // 2
partitionY = (x + y + 1) // 2 – partitionX

# Если partitionX равен 0, то maxLeftX = -inf
# Если partitionX равен x, то minRightX = inf
maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX – 1]
minRightX = float('inf') if partitionX == x else nums1[partitionX]

maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY – 1]
minRightY = float('inf') if partitionY == y else nums2[partitionY]

if maxLeftX <= minRightY and maxLeftY <= minRightX:
# Нашли правильное разделение
# Проверяем четность общего количества элементов
if (x + y) % 2 == 0:
return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
else:
return max(maxLeftX, maxLeftY)
elif maxLeftX > minRightY:
# Смещаем разделение влево
high = partitionX – 1
else:
# Смещаем разделение вправо
low = partitionX + 1

# Пример использования
nums1 = [1, 3]
nums2 = [2]
print(find_median_naive(nums1, nums2)) # 2.0
print(find_median_efficient(nums1, nums2)) # 2.0

nums1 = [1, 2]
nums2 = [3, 4]
print(find_median_naive(nums1, nums2)) # 2.5
print(find_median_efficient(nums1, nums2)) # 2.5

Эффективное решение использует бинарный поиск для поиска правильного разделения массивов, что позволяет достичь логарифмической временной сложности O(log(min(n,m))).

Эти практические примеры демонстрируют, как выбор правильного алгоритма может значительно повысить эффективность решения задач программирования. Для многих стандартных задач оптимизированные алгоритмы поиска и сортировки становятся ключом к написанию производительного кода на Python. 🚀

Овладев основными алгоритмами поиска и сортировки в Python, вы получаете не просто теоретические знания, а мощный практический инструментарий. Умение выбрать оптимальный алгоритм для конкретной задачи — это то, что отличает опытного разработчика от новичка. Независимо от того, работаете ли вы с небольшими наборами данных или обрабатываете терабайты информации, эффективные алгоритмы становятся фундаментом качественных решений. Продолжайте практиковаться, анализируйте производительность вашего кода и не бойтесь экспериментировать с различными подходами — только так можно достичь мастерства в программировании.

Читайте также

• Математика в Python-программировании: ключ к эффективным алгоритмам
• Последовательность Фибоначчи на Python: от рекурсии к оптимизации
• Хэш-таблицы в Python: принцип работы и оптимизация кода
• Подготовка к собеседованию: алгоритмические задачи на Python и LeetCode
• Деревья и графы в Python: алгоритмы, структуры данных, решения
• 3 эффективных способа инверсии списков в Python: что выбрать
• 10 главных операций с массивами Python для эффективной обработки данных
• Визуализация алгоритмов в Python: 5 лучших библиотек для блок-схем
• Множества в Python: как эффективно находить пересечения данных