Примеры задач для линейного и бинарного поиска

3.1 Задача на нахождение элемента в массиве с использованием линейного поиска

Задача: Дан массив чисел. Необходимо найти индекс заданного числа с использованием линейного поиска. Если число не найдено, вернуть -1.

Пример:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Пример использования:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Элемент {target} найден на индексе {result}")  # Вывод: Элемент 7 найден на индексе 2

# Пример использования для элемента, которого нет в массиве:
target = 5
result = linear_search(arr, target)
print(f"Элемент {target} найден на индексе {result}")  # Вывод: Элемент 5 найден на индексе -1

Пояснение:

• Функция linear_search проходит по каждому элементу массива arr и сравнивает его с target.
• Если элемент найден, возвращается его индекс.
• Если все элементы проверены и искомое значение не найдено, функция возвращает -1.

Пошаговое выполнение:

1. Массив [4, 2, 7, 1, 9, 3] и искомое значение 7.
2. Начало поиска: сравнивается первый элемент (4) с 7 — не совпадает.
3. Переход к следующему элементу (2) — не совпадает.
4. Переход к следующему элементу (7) — совпадает.
5. Возврат индекса 2.

3.2 Задача на нахождение элемента в отсортированном массиве с использованием бинарного поиска

Задача: Дан отсортированный массив чисел. Необходимо найти индекс заданного числа с использованием бинарного поиска. Если число не найдено, вернуть -1.

Пример:

def binary_search(arr, target):
    left, right = 0, 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

# Пример использования:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Элемент {target} найден на индексе {result}")  # Вывод: Элемент 7 найден на индексе 3

# Пример использования для элемента, которого нет в массиве:
target = 6
result = binary_search(sorted_array, target)
print(f"Элемент {target} найден на индексе {result}")  # Вывод: Элемент 6 найден на индексе -1

Пояснение:

• Функция binary_search использует два указателя (left и right), чтобы отслеживать границы поиска в массиве arr.
• На каждой итерации находится средний элемент массива и сравнивается с target.
• Если средний элемент равен target, возвращается его индекс.
• Если target меньше среднего элемента, поиск продолжается в левой половине массива.
• Если target больше среднего элемента, поиск продолжается в правой половине массива.
• Если границы пересекаются и элемент не найден, возвращается -1.

Пошаговое выполнение:

1. Отсортированный массив [1, 3, 5, 7, 9, 11, 13] и искомое значение 7.
2. Начальные границы поиска: left = 0, right = 6.
3. Нахождение среднего элемента: mid = (0 + 6) // 2 = 3.
4. Сравнение среднего элемента (7) с target (7) — совпадает.
5. Возврат индекса 3.

3.3 Сравнение и выбор подходящего алгоритма поиска для различных задач

Сравнение линейного и бинарного поиска:

Выбор подходящего алгоритма

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

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

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

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

3.4 Практические задания для закрепления материала

Задание 1: Линейный поиск

Дан массив чисел. Напишите функцию для поиска заданного числа с использованием линейного поиска. Функция должна возвращать индекс найденного элемента или -1, если элемент не найден.

Пример:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Пример использования:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Элемент {target} найден на индексе {result}")  # Вывод: Элемент 7 найден на индексе 2

# Дополнительные тесты:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Задание 2: Бинарный поиск

Дан отсортированный массив чисел. Напишите функцию для поиска заданного числа с использованием бинарного поиска. Функция должна возвращать индекс найденного элемента или -1, если элемент не найден.

Пример:

def binary_search(arr, target):
    left, right = 0, 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

# Пример использования:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Элемент {target} найден на индексе {result}")  # Вывод: Элемент 7 найден на индексе 3

# Дополнительные тесты:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Задание 3: Сравнение линейного и бинарного поиска

Дан массив чисел. Напишите две функции для поиска заданного числа: одну с использованием линейного поиска, другую с использованием бинарного поиска. Сравните производительность обеих функций на больших массивах.

Пример:

import time
import random

# Линейный поиск
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Бинарный поиск
def binary_search(arr, target):
    left, right = 0, 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

# Генерация большого массива
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# Сравнение производительности
start_time = time.time()
linear_search(large_array, target)
print(f"Линейный поиск занял: {time.time() - start_time:.6f} секунд")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Бинарный поиск занял: {time.time() - start_time:.6f} секунд")