Ternary Search Algorithm

Get this book -> Problems on Array: For Interviews and Competitive Programming

Algorithm
Complexity
Implementations
Applications
Discussions

Ternary search is a divide-and-conquer search algorithm. It is mandatory for the array (in which you will search for an element) to be sorted before we begin the search. In this search, after each iteration it neglects ⅓ part of the array and repeats the same operations on the remaining ⅔.

Algorithm

The steps involved in this algorithm are:
(The list must be in sorted order)

Step 1: Divide the search space (initially, the list) in three parts (with two mid-points: mid1 and mid2)
Step 2: The target element is compared with the edge elements that is elements at location mid1, mid2 and the end of the search space. If element matches, go to step 3 else predict in which section the target element lies. The search space is reduced to 1/3rd. If the element is not in the list, go to step 4 or to step 1.
Step 3: Element found. Return index and exit.
Step 4: Element not found. Exit.

Complexity

Worst case time complexity: O(log N)
Average case time complexity: O(log N)
Best case time complexity: O(1)
Space complexity: O(1)

Implementations

Implementation of Linear search algorithm in 16 languages that includes C, C++, Java, Go, JavaScript, PHP, Python, Rust and Swift.

C
C++
Java
Go
JavaScript
PHP
Python
Rust
Kotlin

Tab 1


#include <stdio.h>
int ternarySearch(int array[], int left, int right, int x)
{
   if (right >= left) {
     int intvl = (right - left) / 3;
     int leftmid = left + intvl;
     int rightmid = leftmid + intvl;
     if (array[leftmid] == x)
        return leftmid;
     if (array[rightmid] == x)
        return rightmid;
     if (x < array[leftmid]) {
       return ternarySearch(array, left, leftmid, x);
     }
     else if (x > array[leftmid] && x < array[rightmid]) {
       return ternarySearch(array, leftmid, rightmid, x);
     }
     else {
       return ternarySearch(array, rightmid, right, x);
     }
   }
   return -1;
}
int main(void)
{
   int array[] = {1, 2, 3, 5};
   int size = sizeof(array)/ sizeof(array[0]);
   int find = 3;
   printf("Position of %d is %d\n", find, ternarySearch(array, 0, size-1, find));
   return 0;
}

Tab 2


/*
Part of Cosmos by OpenGenus Foundation
Ternary Search Uses Divide And Conquer Technique
ternary search synopsis
namespace ternary_search_impl
{
template<typename _RandomAccessIter,
         typename _ValueType = typename std::iterator_traits<_RandomAccessIter>::value_type,
         typename _Less>
_RandomAccessIter
ternarySearchImpl(_RandomAccessIter first,
                  _RandomAccessIter last,
                  const _RandomAccessIter ¬FoundSentinel,
                  const _ValueType &find,
                  _Less less);
} // ternary_search_impl
template<typename _RandomAccessIter,
         typename _ValueType = typename std::iterator_traits<_RandomAccessIter>::value_type,
         typename _Less>
_RandomAccessIter
ternarySearch(_RandomAccessIter begin, _RandomAccessIter end, const _ValueType &find, _Less less);
template<typename _RandomAccessIter,
         typename _ValueType = typename std::iterator_traits<_RandomAccessIter>::value_type>
_RandomAccessIter
ternarySearch(_RandomAccessIter begin, _RandomAccessIter end, const _ValueType &find);
*/
#include <functional>
namespace ternary_search_impl
{
template<typename _RandomAccessIter,
         typename _ValueType = typename std::iterator_traits<_RandomAccessIter>::value_type,
         typename _Less>
_RandomAccessIter
ternarySearchImpl(_RandomAccessIter first,
                  _RandomAccessIter last,
                  const _RandomAccessIter ¬FoundSentinel,
                  const _ValueType &find,
                  _Less less)
{
    if (first <= last)
    {
        auto dist = std::distance(first, last);
        auto leftMid = first + dist / 3, rightMid = last - dist / 3;
        auto lessThanLeftMid = less(find, *leftMid), greaterThanLeftMid = less(*leftMid, find),
             lessThanRightMid = less(find, *rightMid), greaterThanRightMid = less(*rightMid, find);
        if (lessThanLeftMid == greaterThanLeftMid)
            return leftMid;
        if (lessThanRightMid == greaterThanRightMid)
            return rightMid;
        if (lessThanLeftMid)
            return ternarySearchImpl(first, leftMid - 1, notFoundSentinel, find, less);
        else if (greaterThanRightMid)
            return ternarySearchImpl(rightMid + 1, last, notFoundSentinel, find, less);
        else
            return ternarySearchImpl(leftMid + 1, rightMid - 1, notFoundSentinel, find, less);
    }
    return notFoundSentinel;
}
} // ternary_search_impl
template<typename _RandomAccessIter,
         typename _ValueType = typename std::iterator_traits<_RandomAccessIter>::value_type,
         typename _Less>
_RandomAccessIter
ternarySearch(_RandomAccessIter begin, _RandomAccessIter end, const _ValueType &find, _Less less)
{
    if (begin < end)
    {
        auto res = ternary_search_impl::ternarySearchImpl(begin, end - 1, end, find, less);
    return res == end ? end : res;
}

return end;

}

template<typename _RandomAccessIter,

typename _ValueType = typename std::iterator_traits<_RandomAccessIter>::value_type>

_RandomAccessIter

ternarySearch(_RandomAccessIter begin, _RandomAccessIter end, const _ValueType &find)

{

return ternarySearch(begin, end, find, std::less<_ValueType>());

}

Tab 3


  public class TSearch{
  public static void main(String[] args) {
    //declare a string array with initial size
    String[] songs = {"Ace", "Space", "Diamond"};
    System.out.println("\nTest binary (String):");
    System.out.println(search(songs, "Ace", 0, 3));
}
public static int search(String[] x, String target, int start, int end) {
    if (start < end) {
        int midpoint1 = start + (end - start) / 3;
        int midpoint2 = start + 2 * (end - start) / 3;
        if (target.compareTo(x[midpoint1]) == 0) {
            return midpoint1;
        } else if (target.compareTo(x[midpoint2]) == 0) {
            return midpoint2;
        } else if (x[midpoint1].compareTo(x[midpoint2]) < 0) {
            return search(x, target, midpoint1, end);
        } else {
            return search(x, target, start, midpoint2);
        }
    }
    return -1;
}
}

Tab 4


package main
import (
  "fmt"
)
// Part of Cosmos by OpenGenus Foundation
func ternarySearch(data []int, left int, right int, value int) int {
  if right >= left {
    mid1 := left + (right-left)/3
    mid2 := right - (right-left)/3
    if data[mid1] == value {
      return mid1
    }
    if data[mid2] == value {
      return mid2
    }
    if value < data[mid1] {
      return ternarySearch(data, left, mid1-1, value)
    } else if value > data[mid2] {
      return ternarySearch(data, mid2+1, right, value)
    } else {
      return ternarySearch(data, mid1+1, mid2-1, value)
    }
  }
  return -1
}
func main() {
  values := []int{1, 2, 3, 4, 5, 12, 30, 35, 46, 84}
  fmt.Println(ternarySearch(values, 0, len(values)-1, 5))
  fmt.Println(ternarySearch(values, 0, len(values)-1, 7))
}

Tab 5


/*
* Part of Cosmos by OpenGenus Foundation
*/
function ternarySearch(givenList, left, right, absolutePrecision) {
  while (true) {
    if (Math.abs(right - left) < absolutePrecision) {
      return (left + right) / 2;
    }
    var leftThird = left + (right - left) / 3;
    var rightThird = right - (right - left) / 3;
    if (givenList[leftThird] < givenList[rightThird]) {
      left = leftThird;
    } else {
      right = rightThird;
    }
  }
}

Tab 6


<?php
/*
 * Part of Cosmos by OpenGenus Foundation
 * @param array $array
 * @param int   $low
 * @param int   $high
 * @param int   $search
 *
 * @return int
 */
function ternarySearch(array $array, $low, $high, $search)
{
    if ($high >= $low) {
        list($lowMiddle, $highMiddle) = [$low + ($high - $low) / 3, $low + 2 * ($high - $low) / 3];
        if ($search === $array[$lowMiddle]) {
            return $lowMiddle;
        } else if ($search === $array[$highMiddle]) {
            return $highMiddle;
        } else if ($search < $array[$highMiddle]) {
            return ternarySearch($array, $low, $lowMiddle, $search);
        } else if ($search > $array[$lowMiddle] && $search < $array[$highMiddle]) {
            return ternarySearch($array, $lowMiddle, $highMiddle, $search);
        } else {
            return ternarySearch($array, $highMiddle, $high, $search);
        }
    }
    return -1;
}
echo sprintf(
    "Position of %d is %d\n",
    $search = 33, ternarySearch($array = [7, 11, 13, 33, 66], 0, count($array) - 1, $search)
);

Tab 7


  def ternarySearch(arr, to_find):
    left = 0
    right = len(arr) - 1
    while left <= right:
        temp2 = left + (right - left) // 3
        temp3 = left + 2 * (right - left) // 3
        if to_find == arr[left]:
            return left
        elif to_find == arr[right]:
            return right
        elif to_find < arr[left] or to_find > arr[right]:
            return -1
        elif to_find <= arr[temp2]:
            right = temp2
        elif to_find > arr[temp2] and to_find <= arr[temp3]:
            left = temp2 + 1
            right = temp3
        else:
            left = temp3 + 1
    return -1
def test(x):
    arr = [6, 15, 18, 44, 47, 87, 97]
    index = ternarySearch(arr, x)
    if index != -1:
        print "The element", x, "is at the index", index
    else:
        print "Element", x, "not found!"
test(44)

Tab 8


// Part of Cosmos by OpenGenus Foundation
fn main() {
    let nums = vec![1, 3, 5, 7, 9];
    let ele = 5;
    println!("Sample input list: {:?}", nums);
    println!("Searched for {} and found index {}", ele, ternary_search(&nums, 0, nums.len(), ele));
}
fn ternary_search(nums: &Vec<i64>, left: usize, right: usize, x: i64) -> i64 {
    if left <= right {
        let intvl = (right - left) / 3;
        let leftmid = left + intvl;
        let rightmid = leftmid + intvl;
       if nums[leftmid] == x {
           return leftmid as i64
       }
       if nums[rightmid] == x {
           return rightmid as i64;
       }
       if x < nums[leftmid] {
           return ternary_search(&nums, left, leftmid, x);
       }
       else if x > nums[leftmid] && x < nums[rightmid] {
           return ternary_search(&nums, leftmid, rightmid, x);
       }
       else {
           return ternary_search(&nums, rightmid, right, x);
       }
   }
   -1
}

Tab 9


// Part of Cosmos by OpenGenus Foundation
fun <T : Comparable<T>> ternarySearch(a: Array<T>, target: T, start: Int = 0, end: Int = a.size): Int {
    if (start < end) {
        val midpoint1 : Int = start + (end - start) / 3
        val midpoint2 : Int = start + 2 * (end - start) / 3
        return when (target) {
            a[midpoint1] -> midpoint1
            a[midpoint2] -> midpoint2
            a[midpoint1] < a[midpoint2] -> ternarySearch(a, target, midpoint1, end)
            else -> ternarySearch(a, target, start, midpoint2)
        }
    }
    return -1
}
fun main(args: Array<String>) {
    val sample: Array<Int> = arrayOf(13, 17, 19, 23, 29, 31, 37, 41, 43)
    val key = 23
val result = ternarySearch(sample, key)

println(when (result) {
    -1 -&gt; "$key is not in $sample"
    else -&gt; "Position of $key is $result"
})

}

Applications

This concept is used in unimodal functions to determine the maximum or minimum value of that function. Unimodal functions are functions that, have a single highest value.
Can be used to search for where the derivative is zero in Newton's method as an optimization.