Iterative Ternary Search Algorithm
The Iterative Ternary Search Algorithm is an advanced searching technique that helps in identifying the maximum or minimum value of a unimodal function. It is an optimization algorithm that narrows down the search range by dividing the given interval into three equal parts and subsequently comparing the function values at the two dividing points. The main idea behind this algorithm is to eliminate one-third of the search space in each iteration, thereby reducing the time complexity and making it more efficient than the traditional binary search algorithm.
The algorithm starts by initializing two pointers, left and right, at the beginning and end of the search interval, respectively. In each iteration, the interval is divided into three equal parts by calculating two midpoints, mid1 and mid2. The function values at these midpoints are then compared, and the search interval is updated accordingly. If the function value at mid1 is less than the value at mid2, it implies that the desired maximum or minimum value lies in the right portion of the interval, so the left pointer is updated to mid1. Conversely, if the function value at mid1 is greater than the value at mid2, the desired value lies in the left portion of the interval, and the right pointer is updated to mid2. The algorithm continues iterating until the search interval converges to the desired maximum or minimum value or reaches a pre-defined level of accuracy.
package Searches;
import java.util.Arrays;
import java.util.Random;
import java.util.stream.Stream;
import static java.lang.String.format;
/**
* A iterative version of a ternary search algorithm
* This is better way to implement the ternary search, because a recursive version adds some overhead to a stack.
* But in java the compile can transform the recursive version to iterative implicitly,
* so there are no much differences between these two algorithms
* <p>
* Worst-case performance Θ(log3(N))
* Best-case performance O(1)
* Average performance Θ(log3(N))
* Worst-case space complexity O(1)
*
* @author Podshivalov Nikita (https://github.com/nikitap492)
* @see SearchAlgorithm
* @see TernarySearch
* @since 2018-04-13
*/
public class IterativeTernarySearch implements SearchAlgorithm {
@Override
public <T extends Comparable<T>> int find(T[] array, T key) {
int left = 0;
int right = array.length - 1;
while (right > left) {
int leftCmp = array[left].compareTo(key);
int rightCmp = array[right].compareTo(key);
if (leftCmp == 0) return left;
if (rightCmp == 0) return right;
int leftThird = left + (right - left) / 3 + 1;
int rightThird = right - (right - left) / 3 - 1;
if (array[leftThird].compareTo(key) <= 0) {
left = leftThird;
} else {
right = rightThird;
}
}
return -1;
}
public static void main(String[] args) {
//just generate data
Random r = new Random();
int size = 100;
int maxElement = 100000;
Integer[] integers = Stream.generate(() -> r.nextInt(maxElement))
.limit(size)
.sorted()
.toArray(Integer[]::new);
//the element that should be found
Integer shouldBeFound = integers[r.nextInt(size - 1)];
IterativeTernarySearch search = new IterativeTernarySearch();
int atIndex = search.find(integers, shouldBeFound);
System.out.println(format("Should be found: %d. Found %d at index %d. An array length %d",
shouldBeFound, integers[atIndex], atIndex, size));
int toCheck = Arrays.binarySearch(integers, shouldBeFound);
System.out.println(format("Found by system method at an index: %d. Is equal: %b",
toCheck, toCheck == atIndex));
}
}
