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

Что такое троичный поиск?
Тернарный поиск — это алгоритм «разделяй и властвуй», используемый для поиска максимального или минимального значения в унимодальной функции. Унимодальная функция — это функция, которая увеличивается, а затем уменьшается (или наоборот) в заданном диапазоне. Основная идея троичного поиска — разделить пространство поиска на три равные части и определить, какая часть содержит искомое значение.

Метод 1: итеративный подход
Давайте начнем с простого итеративного подхода к реализации троичного поиска. Мы определяем два указателя: leftи right, которые представляют собой начальную и конечную точки диапазона поиска. Мы продолжаем делить диапазон на три части, пока не найдем нужное значение или не сузим пространство поиска до одного элемента.

def ternary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        left_third = left + (right - left) // 3
        right_third = right - (right - left) // 3
        if arr[left_third] == target:
            return left_third
        elif arr[right_third] == target:
            return right_third
        elif target < arr[left_third]:
            right = left_third - 1
        elif target > arr[right_third]:
            left = right_third + 1
        else:
            left = left_third + 1
            right = right_third - 1
    return -1

Метод 2: рекурсивный подход
Если вы предпочитаете рекурсивную реализацию, вот другой метод:

def ternary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    left_third = left + (right - left) // 3
    right_third = right - (right - left) // 3
    if arr[left_third] == target:
        return left_third
    elif arr[right_third] == target:
        return right_third
    elif target < arr[left_third]:
        return ternary_search_recursive(arr, target, left, left_third - 1)
    elif target > arr[right_third]:
        return ternary_search_recursive(arr, target, right_third + 1, right)
    else:
        return ternary_search_recursive(arr, target, left_third + 1, right_third - 1)

Метод 3: троичный поиск при поиске локального минимума
Помимо поиска определенного значения, троичный поиск также можно использовать для поиска локального минимума в функции. Подход аналогичен, но вместо сравнения с целевым значением мы сравниваем значения функции в левой и правой трети, чтобы определить направление движения.

def ternary_search_local_min(arr, left, right):
    if left > right:
        return -1
    left_third = left + (right - left) // 3
    right_third = right - (right - left) // 3
    if arr[left_third] < arr[right_third]:
        return ternary_search_local_min(arr, left, right_third - 1)
    elif arr[left_third] > arr[right_third]:
        return ternary_search_local_min(arr, left_third + 1, right)
    else:
        return ternary_search_local_min(arr, left_third + 1, right_third - 1)

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