Тернарный поиск - алгоритм нахождения заданного элемента в отсортированном массиве. В отличии от бинарного поиска, массив разбивается на три части и рекурсивно вызывается от одной из трех частей. Так продолжается до тех пор пока мы либо не найдем элемент, либо пока нужная треть массива не окажется пустой.
Описание алгоритма
Алгоритм тернарного поиска работает следующим образом:
- Разбиваем массив на 3 части и сравниваем искомый элемент с двумя граничными точками
- Если элементы совпадают, то возвращаем индекс
- вызываемся рекурсивно от нужной трети массива
Визуализация работы алгоритма
Рекурсивная реализация алгоритма
int TernarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid1 = l + (r - l)/3;
int mid2 = mid1 + (r - l)/3;
// If x is present at the mid1
if (arr[mid1] == x) return mid1;
// If x is present at the mid2
if (arr[mid2] == x) return mid2;
// If x is present in left one-third
if (arr[mid1] > x) return ternarySearch(arr, l, mid1 - 1, x);
// If x is present in right one-third
if (arr[mid2] < x) return ternarySearch(arr, mid2 + 1, r, x);
// If x is present in middle one-third
return ternarySearch(arr, mid1 + 1, mid2 - 1, x);
}
// We reach here when element is not present in array
return -1;
}
Итеративная реализация алгоритма
int ternarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid1 = l + (r - l)/3;
int mid2 = mid1 + (r - l)/3;
// If x is present at the mid1
if (arr[mid1] == x) return mid1;
// If x is present at the mid2
if (arr[mid2] == x) return mid2;
// If x is present in left one-third
if (arr[mid1] > x) return ternarySearch(arr, l, mid1-1, x);
// If x is present in right one-third
if (arr[mid2] < x) return ternarySearch(arr, mid2+1, r, x);
// If x is present in middle one-third
return ternarySearch(arr, mid1+1, mid2-1, x);
}
// We reach here when element is not present in array
return -1;
}
Рекуррентное уравнение
Рекуррентное уравнение выражащее время работы бинарного поиска имеет вид $$T(n)=T(n/3)+4$$. С помощью основной теоремы (случай 2) находим $$T(n) = \Theta(\log n)$$.
From the first look, it seems the ternary search does less number of comparisons as it makes Log3n recursive calls, but binary search makes Log2n recursive calls. Let us take a closer look.
The following is recursive formula for counting comparisons in worst case of Binary Search.
T(n) = T(n/2) + 2, T(1) = 1
The following is recursive formula for counting comparisons in worst case of Ternary Search.
T(n) = T(n/3) + 4, T(1) = 1
In binary search, there are 2Log2n + 1 comparisons in worst case. In ternary search, there are 4Log3n + 1 comparisons in worst case.
Time Complexity for Binary search = 2clog_2n + O(1)
Time Complexity for Ternary search = 4clog_3n + O(1)
Therefore, the comparison of Ternary and Binary Searches boils down the comparison of expressions 2Log3n and Log2n . The value of 2Log3n can be written as (2 / Log23) * Log2n . Since the value of (2 / Log23) is more than one, Ternary Search does more comparisons than Binary Search in worst case.
Характеристики алгоритма
| Класс алгоритма | Алгоритм поиска |
|---|---|
| Парадигма алгоритма | Разделяй и властвуй |
| Структура данных | Отсортированный массив |
| Худший случай | $$\mathcal{O}(\log n)$$ |
| Лучший случай | $$\mathcal{O}(1)$$ |
| Средний случай | $$\mathcal{O}(\log n)$$ |
| Затраты на память | $$\mathcal{O}(1)$$ для итеративной версии, $$\mathcal{O}(\log n)$$ для рекурсивной версии |