Ternary Search Algorithm Code Implementations
Complete Ternary Search Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Ternary Search Algorithm Guide ยท Launch Interactive Visualizer
C++ Implementation
// Ternary Search Implementation in C++
#include <iostream>
#include <vector>
#include <functional>
class TernarySearch {
public:
static int ternarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
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;
}
// Ternary Search for unimodal function maximum
static double ternarySearchMax(std::function<double(double)> func,
double left, double right, double precision = 1e-6) {
while (right - left > precision) {
double mid1 = left + (right - left) / 3;
double mid2 = right - (right - left) / 3;
if (func(mid1) < func(mid2)) {
left = mid1;
} else {
right = mid2;
}
}
return (left + right) / 2;
}
// Ternary Search for unimodal function minimum
static double ternarySearchMin(std::function<double(double)> func,
double left, double right, double precision = 1e-6) {
while (right - left > precision) {
double mid1 = left + (right - left) / 3;
double mid2 = right - (right - left) / 3;
if (func(mid1) > func(mid2)) {
left = mid1;
} else {
right = mid2;
}
}
return (left + right) / 2;
}
};JAVA Implementation
// Ternary Search Implementation in Java
public class TernarySearch {
public static int ternarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
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;
}
// Ternary Search for unimodal function maximum
public static double ternarySearchMax(java.util.function.DoubleFunction<Double> func,
double left, double right, double precision) {
while (right - left > precision) {
double mid1 = left + (right - left) / 3;
double mid2 = right - (right - left) / 3;
if (func.apply(mid1) < func.apply(mid2)) {
left = mid1;
} else {
right = mid2;
}
}
return (left + right) / 2;
}
// Ternary Search for unimodal function minimum
public static double ternarySearchMin(java.util.function.DoubleFunction<Double> func,
double left, double right, double precision) {
while (right - left > precision) {
double mid1 = left + (right - left) / 3;
double mid2 = right - (right - left) / 3;
if (func.apply(mid1) > func.apply(mid2)) {
left = mid1;
} else {
right = mid2;
}
}
return (left + right) / 2;
}
}JAVASCRIPT Implementation
// Ternary Search Implementation in JavaScript
function ternarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid1 = left + Math.floor((right - left) / 3);
const mid2 = right - Math.floor((right - left) / 3);
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;
}
// Ternary Search for unimodal function maximum
function ternarySearchMax(func, left, right, precision = 1e-6) {
while (right - left > precision) {
const mid1 = left + (right - left) / 3;
const mid2 = right - (right - left) / 3;
if (func(mid1) < func(mid2)) {
left = mid1;
} else {
right = mid2;
}
}
return (left + right) / 2;
}
// Ternary Search for unimodal function minimum
function ternarySearchMin(func, left, right, precision = 1e-6) {
while (right - left > precision) {
const mid1 = left + (right - left) / 3;
const mid2 = right - (right - left) / 3;
if (func(mid1) > func(mid2)) {
left = mid1;
} else {
right = mid2;
}
}
return (left + right) / 2;
}PYTHON Implementation
# Ternary Search Implementation in Python
def ternary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid1 = left + (right - left) // 3
mid2 = right - (right - left) // 3
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 = mid1 + 1
right = mid2 - 1
return -1
# Ternary Search for unimodal function maximum
def ternary_search_max(func, left, right, precision=1e-6):
while right - left > precision:
mid1 = left + (right - left) / 3
mid2 = right - (right - left) / 3
if func(mid1) < func(mid2):
left = mid1
else:
right = mid2
return (left + right) / 2
# Ternary Search for unimodal function minimum
def ternary_search_min(func, left, right, precision=1e-6):
while right - left > precision:
mid1 = left + (right - left) / 3
mid2 = right - (right - left) / 3
if func(mid1) > func(mid2):
left = mid1
else:
right = mid2
return (left + right) / 2