AntInLoop

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