Ternary Search
Ternary Search divides the search space into three parts per step using two mid-points (M1 and M2), eliminating one third each iteration. Theoretically requires more comparisons than Binary Search due to the higher base of the logarithm.
Search Target
↑ Set a target value above to begin searching the array
Legend
Inspector
Legend
Inspector
Reference implementation of Ternary Search. Select a language tab to view and copy the code.
int ternary_search(int arr[], int left, int right, int target) {
while (left <= right) {
int third = (right - left) / 3;
int mid1 = left + third;
int mid2 = right - third;
if (arr[mid1] == target) return mid1;
if (arr[mid2] == target) return mid2;
if (target < arr[mid1]) right = mid1 - 1;
else if (target > arr[mid2]) left = mid2 + 1;
else { left = mid1 + 1; right = mid2 - 1; }
}
return -1;
}#include <vector>
int ternarySearch(const std::vector<int>& arr, int target) {
int left = 0, right = static_cast<int>(arr.size()) - 1;
while (left <= right) {
int third = (right - left) / 3;
int mid1 = left + third;
int mid2 = right - third;
if (arr[mid1] == target) return mid1;
if (arr[mid2] == target) return mid2;
if (target < arr[mid1]) right = mid1 - 1;
else if (target > arr[mid2]) left = mid2 + 1;
else { left = mid1 + 1; right = mid2 - 1; }
}
return -1;
}public static int ternarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int third = (right - left) / 3;
int mid1 = left + third;
int mid2 = right - third;
if (arr[mid1] == target) return mid1;
if (arr[mid2] == target) return mid2;
if (target < arr[mid1]) right = mid1 - 1;
else if (target > arr[mid2]) left = mid2 + 1;
else { left = mid1 + 1; right = mid2 - 1; }
}
return -1;
}def ternary_search(arr: list[int], target: int) -> int:
left, right = 0, len(arr) - 1
while left <= right:
third = (right - left) // 3
mid1 = left + third
mid2 = right - third
if arr[mid1] == target: return mid1
if arr[mid2] == target: return mid2
if target < arr[mid1]: right = mid1 - 1
elif target > arr[mid2]: left = mid2 + 1
else:
left, right = mid1 + 1, mid2 - 1
return -1function ternarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const third = Math.floor((right - left) / 3);
const mid1 = left + third;
const mid2 = right - third;
if (arr[mid1] === target) return mid1;
if (arr[mid2] === target) return mid2;
if (target < arr[mid1]) right = mid1 - 1;
else if (target > arr[mid2]) left = mid2 + 1;
else { left = mid1 + 1; right = mid2 - 1; }
}
return -1;
}Python — Code Walkthrough
Floor division for third
third = (right - left) // 3Python's // operator performs floor division, keeping third an integer. For a window of 10 elements: third = 3, mid1 = left+3, mid2 = right−3, giving three segments of sizes 3, 3, 4.
Compact single-line returns
if arr[mid1] == target: return mid1Python allows the if body on the same line as the colon when it's a single statement. This style is acceptable for short early returns but should not be overused.
elif chain — four segments
if ... elif ... else: left, right = mid1+1, mid2-1Python elif avoids deeply nested ifs. The final else clause narrows both bounds simultaneously using tuple assignment — idiomatic Python.
Tuple swap for middle segment
left, right = mid1 + 1, mid2 - 1Multiple assignment updates both bounds in a single statement. The right-hand side is fully evaluated before any assignment occurs, so no temp variable is needed.