Ternary search algorithm:

Category : Data-structures-algorithms | Sub Category : Search Algorithms | By Runner Dev Last updated: 2020-11-05 11:55:57 Viewed : 173

Ternary search algorithm:

A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function The algorithm determines either that the minimum or maximum cannot be in the first third of the domain or that it cannot be in the last third of the domain, then repeats on the remaining third.

Worst-case performance (log3(N))

Best-case performance O(1)

Average performance (log3(N))

Worst-case space complexity O(1)

1. Sample Algorithm :-

function ternarySearch(f, left, right, absolutePrecision)
//left and right are the current bounds; the maximum is between them
if (right-left < absolutePrecision)
return (left+right)/2 leftThird := (left*2+right)/3 rightThird := (left+right*2)/3

if (f(leftThird) < f(rightThird))
return ternarySearch(f, leftThird, right, absolutePrecision)
else
return ternarySearch(f, left, rightThird, absolutePrecision)
end

2. Example:

TernarySearch.java

` package runnerdev; `

import java.util.Arrays;

public class TernarySearch  {

private static <T extends Comparable<T>> int ternarySearch (T[] arr, T key, int start, int end) {

if (start > end) {

return -1;

}

/* First boundary: add 1/3 of length to start */

int mid1 = start + (end - start) / 3;

/* Second boundary: add 2/3 of length to start */

int mid2 = start + 2 * (end - start) / 3;

if (key.compareTo(arr[mid1]) == 0) {

return mid1;

} else if (key.compareTo(arr[mid2]) == 0) {

return mid2;

}

/* Search the first (1/3) rd part of the array. */

else if (key.compareTo(arr[mid1]) < 0) {

return ternarySearch(arr, key, start, --mid1);

}

/* Search 3rd (1/3)rd part of the array */

else if (key.compareTo(arr[mid2]) > 0) {

return ternarySearch(arr, key, ++mid2, end);

}

/* Search middle (1/3)rd part of the array */

else {

return ternarySearch(arr, key, mid1, mid2);

}

}

public static void main(String args[]) {

int l, r, result, key;

Integer array[] = { 11, 22, 3, 14, 25, 16, 27, 18, 29, 10 };

// Sort the array

Arrays.sort(array);

System.out.print("Sorted Array: ");

for (Integer arr : array) {

System.out.print(arr + " ");

}

// Starting index

l = 0;

// length of array

r = array.length;

// Key to be searched in the array

key = 25;

result = ternarySearch(array, key, l, r);

System.out.println(" Index of " + key + " is " + result);

// Key to be searched in the array

key = 150;

result = ternarySearch(array, 5, l, r);

System.out.println("Index of " + key + " is " + result);

}

}

Output:

Sorted Array: 3 10 11 14 16 18 22 25 27 29

Index of 25 is 7

Index of 150 is -1