WikiGalaxy
Ternary Search Overview
Introduction to Ternary Search
Ternary search is a divide-and-conquer search algorithm that splits the array into three parts rather than two, as in binary search. It is particularly useful for unimodal functions where the function increases and then decreases.
public class TernarySearch {
public static int ternarySearch(int[] arr, int l, int r, int key) {
if (r >= l) {
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (arr[mid1] == key) return mid1;
if (arr[mid2] == key) return mid2;
if (key < arr[mid1]) return ternarySearch(arr, l, mid1 - 1, key);
else if (key > arr[mid2]) return ternarySearch(arr, mid2 + 1, r, key);
else return ternarySearch(arr, mid1 + 1, mid2 - 1, key);
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int key = 5;
int index = ternarySearch(arr, 0, arr.length - 1, key);
System.out.println("Index of " + key + ": " + index);
}
}
Console Output:
Index of 5: 4
Ternary Search on Unimodal Function
Unimodal Function Search
Ternary search can efficiently find the maximum or minimum of a unimodal function, which is a function that has a single peak or trough.
public class TernarySearchUnimodal {
public static double ternarySearch(double l, double r, Function f) {
double eps = 1e-9; // precision
while (r - l > eps) {
double mid1 = l + (r - l) / 3;
double mid2 = r - (r - l) / 3;
if (f.apply(mid1) < f.apply(mid2))
l = mid1;
else
r = mid2;
}
return (l + r) / 2;
}
public static void main(String[] args) {
Function f = x -> -1 * (x - 2) * (x - 2) + 3;
double maxX = ternarySearch(-10, 10, f);
System.out.println("Maximum at x = " + maxX);
}
}
Console Output:
Maximum at x = 2.0
Ternary Search for Maximum Element
Finding Maximum in Rotated Array
In a rotated sorted array, ternary search can be used to find the maximum element more efficiently than a linear search.
public class TernarySearchRotatedArray {
public static int findMax(int[] arr, int l, int r) {
if (l == r) return arr[l];
if (r == l + 1) return Math.max(arr[l], arr[r]);
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (arr[mid1] > arr[mid2])
return findMax(arr, l, mid2);
else
return findMax(arr, mid1, r);
}
public static void main(String[] args) {
int[] arr = {4, 5, 6, 7, 1, 2, 3};
int max = findMax(arr, 0, arr.length - 1);
System.out.println("Maximum element: " + max);
}
}
Console Output:
Maximum element: 7
Ternary Search for Minimum Element
Finding Minimum in Rotated Array
Similar to finding the maximum, ternary search can be applied to locate the minimum element in a rotated sorted array.
public class TernarySearchMinRotatedArray {
public static int findMin(int[] arr, int l, int r) {
if (l == r) return arr[l];
if (r == l + 1) return Math.min(arr[l], arr[r]);
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (arr[mid1] < arr[mid2])
return findMin(arr, l, mid2);
else
return findMin(arr, mid1, r);
}
public static void main(String[] args) {
int[] arr = {6, 7, 1, 2, 3, 4, 5};
int min = findMin(arr, 0, arr.length - 1);
System.out.println("Minimum element: " + min);
}
}
Console Output:
Minimum element: 1
Ternary Search with Custom Comparator
Using Custom Comparator
Ternary search can be adapted to use custom comparators, allowing for flexible search conditions beyond simple numerical comparisons.
import java.util.Comparator;
public class TernarySearchCustomComparator {
public static int ternarySearch(T[] arr, int l, int r, T key, Comparator cmp) {
if (r >= l) {
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (cmp.compare(arr[mid1], key) == 0) return mid1;
if (cmp.compare(arr[mid2], key) == 0) return mid2;
if (cmp.compare(key, arr[mid1]) < 0) return ternarySearch(arr, l, mid1 - 1, key, cmp);
else if (cmp.compare(key, arr[mid2]) > 0) return ternarySearch(arr, mid2 + 1, r, key, cmp);
else return ternarySearch(arr, mid1 + 1, mid2 - 1, key, cmp);
}
return -1;
}
public static void main(String[] args) {
Integer[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int key = 7;
int index = ternarySearch(arr, 0, arr.length - 1, key, Integer::compareTo);
System.out.println("Index of " + key + ": " + index);
}
}
Console Output:
Index of 7: 6
