Definition
- Ternary search is a searching algorithm used to find a specific element within a sorted list or array.
- It works by repeatedly dividing the search range into three parts and then narrowing down the search based on comparisons with the elements at the two dividing points.
- This process continues until the desired element is found or the search range is reduced to a single element.
Working of Ternary Search
Imagine you have a sorted list of numbers and you want to find a specific number, let’s say 36. Instead of looking at each number one by one, ternary search helps you narrow down your search range quickly.
1. Dividing into Three Parts
You start by dividing the list into three parts. You pick two points, let’s call them left and right, which divide the list into three segments.
2. Comparing with Midpoints
You compare the number you’re looking for (25) with the elements at the left and right points. This gives you some information about where your target might be located.
3. Adjusting the Search Range
Based on the comparisons, you have three possibilities
- If your target is smaller than the element at left, you know it must be in the left segment.
- If it’s larger than the element at right, you know it’s in the right segment.
- If it’s neither, it’s likely in the middle segment.
4. Reducing the Search Range
You narrow down your search range based on the comparisons. If your target is in the left or right segment, you ignore the other segments. If it’s in the middle segment, you update the left and right points to focus on a smaller range.
5. Repeat the Process
You repeat the above steps with the new, smaller range. You pick new left and right points, compare with the middle elements, and adjust the range again.
6. Continuing until Found
You keep repeating the process until you either find the number 25 or narrow down the search range to just one number. Once you’ve done that, you’ve found your target!
.
Algorithm
- Imagine you have a sorted list, like numbers from small to big.
- First, you find two points that divide the list into three parts: left, middle, and right.
- You compare the item you’re looking for with the items at the left and right points.
- If your item is smaller than the left one, you know it must be in the left part.
- If it’s bigger than the right one, it must be in the right part.
- If it’s neither, it’s likely in the middle part.
.
Source Code for Ternary Search
// COMPUTER GEEK – compgeek.co.in
// Write a program for Ternary Search Algorithm
#include <stdio.h>
// Ternary Search Function
int ternarySearch(int arr[], int left, int right, int target) {
if (left <= right) {
// Calculate the mid points
int mid1 = left + (right – left) / 3;
int mid2 = right – (right – left) / 3;
// Check if target is at mid1 or mid2
if (arr[mid1] == target) {
return mid1;
}
if (arr[mid2] == target) {
return mid2;
}
// Narrow down the search to one of the thirds
if (target < arr[mid1]) {
return ternarySearch(arr, left, mid1 – 1, target);
} else if (target > arr[mid2]) {
return ternarySearch(arr, mid2 + 1, right, target);
} else {
return ternarySearch(arr, mid1 + 1, mid2 – 1, target);
}
}
// Target not found
return -1;
}
int main() {
int n;
printf(“Enter the number of elements in the array: “);
scanf(“%d”, &n);
int arr[n];
printf(“Enter the elements in sorted order:\n”);
for (int i = 0; i < n; i++) \
{
scanf(“%d”, &arr[i]);
}
int target;
printf(“Enter the target element to search for: “);
scanf(“%d”, &target);
int result = ternarySearch(arr, 0, n – 1, target);
if (result == -1) {
printf(“Element not found in the array.\n”);
} else {
printf(“Element found at index %d.\n”, result);
}
return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for Ternary Search Algorithm
#include <iostream>
using namespace std;
// Ternary Search Function
int ternarySearch(int arr[], int left, int right, int target)
{
if (left <= right)
{
// Calculate the mid points
int mid1 = left + (right – left) / 3;
int mid2 = right – (right – left) / 3;
// Check if target is at mid1 or mid2
if (arr[mid1] == target)
{
return mid1;
}
if (arr[mid2] == target)
{
return mid2;
}
// Narrow down the search to one of the thirds
if (target < arr[mid1])
{
return ternarySearch(arr, left, mid1 – 1, target);
}
else if (target > arr[mid2])
{
return ternarySearch(arr, mid2 + 1, right, target);
}
else
{
return ternarySearch(arr, mid1 + 1, mid2 – 1, target);
}
}
// Target not found
return -1;
}
int main()
{
int n;
cout << “Enter the number of elements in the array: “;
cin >> n;
int arr[n];
cout << “Enter the elements in sorted order:” << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
int target;
cout << “Enter the target element to search for: “;
cin >> target;
int result = ternarySearch(arr, 0, n – 1, target);
if (result == -1) {
cout << “Element not found in the array.” << endl;
}
else
{
cout << “Element found at index ” << result << “.” << endl;
}
return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for Ternary Search Algorithm
import java.util.Scanner;
public class TernarySearch {
// Function to perform ternary search
public static int ternarySearch(int[] arr, int left, int right, int target) {
if (left <= right) {
// Calculate the mid points
int mid1 = left + (right – left) / 3;
int mid2 = right – (right – left) / 3;
// Check if target is at mid1 or mid2
if (arr[mid1] == target) {
return mid1;
}
if (arr[mid2] == target) {
return mid2;
}
// Narrow down the search to one of the thirds
if (target < arr[mid1]) {
return ternarySearch(arr, left, mid1 – 1, target);
} else if (target > arr[mid2]) {
return ternarySearch(arr, mid2 + 1, right, target);
} else {
return ternarySearch(arr, mid1 + 1, mid2 – 1, target);
}
}
// Target not found
return -1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print(“Enter the number of elements in the array: “);
int n = scanner.nextInt();
int[] arr = new int[n];
System.out.print(“Enter the elements in sorted order: “);
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
System.out.print(“Enter the target element to search for: “);
int target = scanner.nextInt();
int result = ternarySearch(arr, 0, n – 1, target);
if (result == -1) {
System.out.println(“Element not found in the array.”);
} else {
System.out.println(“Element found at index ” + result + “.”);
}
scanner.close();
}
}
# COMPUTER GEEK – compgeek.co.in
# Write a program for Ternary Search Algorithm
def ternary_search(arr, left, right, target):
if left <= right:
# Calculate the mid points
mid1 = left + (right – left) // 3
mid2 = right – (right – left) // 3
# Check if target is at mid1 or mid2
if arr[mid1] == target:
return mid1
if arr[mid2] == target:
return mid2
# Narrow down the search to one of the thirds
if target < arr[mid1]:
return ternary_search(arr, left, mid1 – 1, target)
elif target > arr[mid2]:
return ternary_search(arr, mid2 + 1, right, target)
else:
return ternary_search(arr, mid1 + 1, mid2 – 1, target)
# Target not found
return -1
def main():
n = int(input(“Enter the number of elements in the array: “))
arr = list(map(int, input(“Enter the elements in sorted order: “).split()))
target = int(input(“Enter the target element to search for: “))
result = ternary_search(arr, 0, n – 1, target)
if result == -1:
print(“Element not found in the array.”)
else:
print(f”Element found at index {result}.”)
# Call the main function
main()
Time Complexity
Ternary search can be really fast, but it’s not always better than binary search.
- In the best case, the time complexity is O(1) for both ternary search and binary search.
- Some of you are thinking that in the average-case, ternary search has less time complexity than binary search because binary search searches the target element in only 1 place (The middle) and ternary search searches the target element in two places (1/3 and 2/3 places). But this is wrong. In an iteration, ternary search has two comparison and binary search has only 1 comparison.
- In the worst case, it takes about log3(n) steps, which is slower than log2(n) steps in binary search.
Space Complexity
The space needed for ternary search is pretty low O(1) because it only requires a few variables to keep track of the positions and comparisons.
Advantages of Ternary search
- Can be faster than binary search when the list has very few possibilities.
- Useful when the list isn’t evenly divided, or you want to find the local maximum or minimum.
Disadvantages of Ternary Search
- Slower than binary search in many cases.
- Works well only on sorted lists.
- More complicated than binary search.
Test Yourself
Q1- Explain the concept of the ternary search algorithm.
The ternary search algorithm is a searching technique used to find a specific element within a sorted list or array. It divides the search range into three parts and compares the target element with elements at two dividing points. Based on these comparisons, it narrows down the search range until the desired element is found or the range becomes a single element.
Q2- Describe a scenario where the ternary search algorithm can be applied effectively.
Ternary search is effective when searching for the maximum or minimum value in a unimodal function. For instance, in optimizing mathematical functions, the algorithm can be used to quickly find the optimal point where a certain value is maximized or minimized.
Q3- Explain the time complexity of the ternary search algorithm.
In the best case, where the target is found immediately, the time complexity is O(1). In the worst case, the algorithm requires approximately log3(n) steps to narrow down the search range to one element.
Q4- Describe a real-life situation where ternary search can be applied creatively.
Ternary search can be applied in identifying optimal tuning parameters in machine learning algorithms. It helps find the parameters that yield the best performance by narrowing down the search space of potential values.
Q5- In which scenario is ternary search less efficient?
When the list is sorted
When the list is unimodal
When the search space is evenly divided
When the search space is not evenly divided
Ans – (4)
Explanation – Ternary search’s efficiency decreases when the search space is not evenly divided into three parts.
Q6- Ternary search is particularly useful for finding
Elements in an unsorted list
Local extremes in unimodal functions
Elements in a sorted list
Global extremes in non-unimodal functions
Ans – (2)
Explanation – Ternary search excels in finding local maximum or minimum points in unimodal functions.
Q7- Ternary search is more efficient than binary search when:
The list is unsorted
The list has a small number of elements
The search space is evenly divided
The list is sorted
Ans – (2)
Explanation – Ternary search can be faster than binary search when the search space is small.
