Что такое алгоритм в информатике

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

Ключевые свойства любого алгоритма:

• Дискретность: Алгоритм состоит из отдельных, последовательных шагов.
• Детерминированность: Каждый шаг строго определён и не допускает двусмысленности. При одинаковых входных данных результат всегда будет одинаковым.
• Конечность: Алгоритм должен завершаться за конечное число шагов.
• Массовость: Алгоритм применим к различным наборам входных данных, а не только к одному конкретному примеру.

Пример: Алгоритм бинарного поиска на Python

Этот алгоритм эффективно находит элемент в отсортированном массиве, многократно деля пополам область поиска.

# arr должен быть отсортирован
def binary_search(arr: list, target: int) -> int:
    low, high = 0, len(arr) - 1

    while low <= high:
        # Находим середину текущего диапазона
        mid = (low + high) // 2
        guess = arr[mid]

        if guess == target:
            return mid  # Элемент найден
        if guess > target:
            high = mid - 1 # Искать в левой половине
        else:
            low = mid + 1  # Искать в правой половине

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

Сложность этого алгоритма — O(log n), что значительно эффективнее линейного поиска (O(n)) для больших объёмов данных.