The Ternary Search Algorithm is a divide-and-conquer search algorithm that splits an array into three parts and determines which part may contain the target value. It is particularly useful for unimodal functions where the function first increases and then decreases.


public class TernarySearch {
  public static int ternarySearch(int l, int r, int key, int[] arr) {
    while (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]) r = mid1 - 1;
      else if (key > arr[mid2]) l = mid2 + 1;
      else { l = mid1 + 1; r = mid2 - 1; }
    }
    return -1;
  }
  public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int key = 5;
    int index = ternarySearch(0, arr.length - 1, key, arr);
    System.out.println("Index of " + key + ": " + index);
  }
}

Algorithm Explanation

The algorithm calculates two mid points in the array and checks if the target value is present at either of these points. If not, it narrows the search to the segment of the array where the target value could exist, thus reducing the search space efficiently.

Console Output:

Index of 5: 4

Ternary Search on Large Array

Use Case: Large Arrays

Ternary search can be particularly effective on large sorted arrays where the cost of evaluating the function is high, and the array size is substantial enough to benefit from the reduced number of comparisons.


public class LargeArrayTernarySearch {
  public static int ternarySearch(int l, int r, int key, int[] arr) {
    while (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]) r = mid1 - 1;
      else if (key > arr[mid2]) l = mid2 + 1;
      else { l = mid1 + 1; r = mid2 - 1; }
    }
    return -1;
  }
  public static void main(String[] args) {
    int[] arr = new int[1000000];
    for (int i = 0; i < arr.length; i++) arr[i] = i;
    int key = 999999;
    int index = ternarySearch(0, arr.length - 1, key, arr);
    System.out.println("Index of " + key + ": " + index);
  }
}

Efficiency in Large Datasets

In this example, the ternary search efficiently finds the index of the key in a large dataset by minimizing the number of required comparisons, showcasing its advantage over linear searches in such scenarios.

Console Output:

Index of 999999: 999999

Ternary Search for Unimodal Functions

Application in Unimodal Functions

Ternary search is particularly useful in scenarios where the function is unimodal, meaning it has a single peak. This makes it ideal for optimization problems where you need to find the maximum or minimum value of a function.


public class UnimodalTernarySearch {
  public static double ternarySearch(double l, double r, double precision, Function f) {
    while (r - l > precision) {
      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 -> -Math.pow(x, 2) + 4 * x + 1;
    double max = ternarySearch(0, 5, 1e-6, f);
    System.out.println("Maximum value at x: " + max);
  }
}

Finding Maximum in Unimodal Functions

This example demonstrates using ternary search to find the maximum value of a quadratic function. By iteratively narrowing the range, we efficiently locate the peak of the function.

Console Output:

Maximum value at x: 2.000000

Ternary Search for String Arrays

String Array Search

Ternary search can also be applied to search within arrays of strings, provided that the strings are sorted lexicographically. This can be useful for dictionary lookups or searching within sorted lists of names.


public class StringArrayTernarySearch {
  public static int ternarySearch(int l, int r, String key, String[] arr) {
    while (r >= l) {
      int mid1 = l + (r - l) / 3;
      int mid2 = r - (r - l) / 3;
      if (arr[mid1].equals(key)) return mid1;
      if (arr[mid2].equals(key)) return mid2;
      if (key.compareTo(arr[mid1]) < 0) r = mid1 - 1;
      else if (key.compareTo(arr[mid2]) > 0) l = mid2 + 1;
      else { l = mid1 + 1; r = mid2 - 1; }
    }
    return -1;
  }
  public static void main(String[] args) {
    String[] arr = {"apple", "banana", "cherry", "date", "fig"};
    String key = "cherry";
    int index = ternarySearch(0, arr.length - 1, key, arr);
    System.out.println("Index of " + key + ": " + index);
  }
}

Lexicographical Search

In this example, the ternary search is adapted to work with strings, allowing for efficient searching through a lexicographically ordered array of words.

Console Output:

Index of cherry: 2

Ternary Search for Floating Point Numbers

Floating Point Precision

Ternary search can be utilized for finding specific values within floating-point arrays, particularly useful in scientific computations where precision is crucial.


public class FloatArrayTernarySearch {
  public static int ternarySearch(int l, int r, double key, double[] arr, double precision) {
    while (r >= l) {
      int mid1 = l + (r - l) / 3;
      int mid2 = r - (r - l) / 3;
      if (Math.abs(arr[mid1] - key) < precision) return mid1;
      if (Math.abs(arr[mid2] - key) < precision) return mid2;
      if (key < arr[mid1]) r = mid1 - 1;
      else if (key > arr[mid2]) l = mid2 + 1;
      else { l = mid1 + 1; r = mid2 - 1; }
    }
    return -1;
  }
  public static void main(String[] args) {
    double[] arr = {0.1, 0.2, 0.3, 0.4, 0.5};
    double key = 0.3;
    int index = ternarySearch(0, arr.length - 1, key, arr, 1e-9);
    System.out.println("Index of " + key + ": " + index);
  }
}

Precision Handling

By using a precision parameter, this implementation of ternary search is capable of finding floating-point numbers with high accuracy, which is essential in domains requiring precise calculations.

Console Output:

Index of 0.3: 2