Обработка массивов: поиск, сортировка

Определение

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

Бинарный поиск — алгоритм поиска в отсортированном массиве, при котором диапазон поиска каждый раз делится пополам.

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

Пример

Линейный поиск

# Линейный поиск элемента в массиве
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # нашли — возвращаем индекс
    return -1  # не нашли

# Пример использования
a = [15, 8, 23, 4, 42, 16, 11]
x = int(input("Что ищем? "))
result = linear_search(a, x)
if result != -1:
    print(f"Элемент найден на позиции {result}")
else:
    print("Элемент не найден")

Трассировка: a = [15, 8, 23, 4, 42, 16, 11], ищем x = 23. i=0: a[0]=15 ≠ 23. i=1: a[1]=8 ≠ 23. i=2: a[2]=23 = 23 → return 2. Ответ: 2.

Бинарный поиск

# Бинарный поиск (массив должен быть отсортирован)
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:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Пример использования
a = [2, 5, 8, 12, 19, 24, 31, 37]
x = int(input("Что ищем? "))
result = binary_search(a, x)
if result != -1:
    print(f"Элемент найден на позиции {result}")
else:
    print("Элемент не найден")

Трассировка: a = [2, 5, 8, 12, 19, 24, 31, 37], ищем x = 24. left=0, right=7. mid=3: a[3]=12 < 24 → left=4. left=4, right=7. mid=5: a[5]=24 = 24 → return 5.

Сортировка

Пузырьковая сортировка

# Пузырьковая сортировка
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Пример использования
a = [5, 3, 8, 1, 9, 2]
print("Было:", a)
bubble_sort(a)
print("Стало:", a)

Трассировка: a = [5, 3, 8, 1, 9, 2], n=6. i=0 (j=0..4): [3,5,1,8,2,9] — 5↔3, 8↔1, 9↔2 i=1 (j=0..3): [3,1,5,2,8,9] — 5↔1, 8↔2 i=2 (j=0..2): [1,3,2,5,8,9] — 3↔1, 5↔2 i=3 (j=0..1): [1,2,3,5,8,9] — 3↔2 i=4 (j=0..0): [1,2,3,5,8,9] — без обменов Результат: [1, 2, 3, 5, 8, 9]

Школьный алгоритмический язык: линейный поиск

алг ЛинейныйПоиск (цел таб arr[1:N], цел target)
арг arr, target
рез цел
нач
  цел i
  нц для i от 1 до N
    если arr[i] = target то
      знач := i
      выход
    все
  кц
  знач := 0
кон

Школьный алгоритмический язык: пузырьковая сортировка

алг ПузырьковаяСортировка (цел таб arr[1:N])
арг arr
рез arr
нач
  цел i, j, tmp
  нц для i от 1 до N-1
    нц для j от 1 до N-i
      если arr[j] > arr[j+1] то
        tmp := arr[j]
        arr[j] := arr[j+1]
        arr[j+1] := tmp
      все
    кц
  кц
кон

Обозначения

Операция	Синтаксис	Описание
Линейный поиск	for i in range(n): if arr[i] == x	O(n), массив не обязательно отсортирован
Бинарный поиск	while left <= right: mid = (l+r)//2	O(log n), массив отсортирован
Пузырьковая сортировка	for i in range(n-1): for j in range(n-1-i): if arr[j] > arr[j+1]: swap	O(n²)
Обмен элементов	a, b = b, a	Меняет значения двух переменных
Поиск максимума	max(arr)	Встроенная функция
Поиск минимума	min(arr)	Встроенная функция

Важно!

• Линейный поиск работает на любом массиве, но медленный на больших данных.
• Бинарный поиск работает только на отсортированном массиве. Если массив не отсортирован — результат непредсказуем.
• Пузырьковая сортировка — простейшая, но неэффективная для больших массивов (O(n²)).
• В задачах ОГЭ внимательно выполняйте трассировку: записывайте состояние массива после каждого прохода.
• При бинарном поиске границы left и right должны обновляться как mid+1 и mid-1 (не mid), иначе возможен бесконечный цикл.
• В школьном алгоритмическом языке индексация начинается с 1, в Python — с 0. Будьте внимательны при переводе.