Learn About Ternary Search In Data Structures (With Examples)

0 min read

Searching algorithms play a crucial role in optimizing data retrieval, especially when working with large datasets. One such efficient searching technique is Ternary Search, a divide-and-conquer algorithm that splits the search space into three parts instead of two, unlike Binary Search. This approach can enhance search efficiency in certain scenarios, particularly when dealing with ordered lists.

In this article, we will explore the working of Ternary Search, its implementation, time complexity, and how it compares with Binary Search.

What Is Ternary Search In Data Structures?

Ternary Search in data structures is a divide-and-conquer searching algorithm used to find the position of a target element in a sorted array. Unlike Binary Search, which splits the search space into two halves, Ternary Search divides it into three equal parts at each step. This results in a slightly different approach to narrowing down the search space.

The algorithm works by selecting two midpoints in the array:

• mid1: The first one-third position of the current search space.
  
• mid2: The second one-third position of the current search space.
  

At each step, we compare the target element with mid1 and mid2 and decide which part of the array to continue searching in:

1. If the target matches mid1, return its index.
   
2. If the target matches mid2, return its index.
   
3. If the target is less than mid1, search in the first third.
   
4. If the target is between mid1 and mid2, search in the middle third.
   
5. If the target is greater than mid2, search in the last third.
   

This process is repeated until the element is found or the search space is exhausted.

Working Of Ternary Search Algorithm

Ternary Search works by repeatedly dividing the search space into three equal parts and narrowing the search range based on comparisons. Let's go through its working in a structured step-by-step manner.

Step 1: Define the Search Space

• Let the given array be sorted.
  
• Define two boundary variables:
  
• low → starting index of the search space.
  
• high → ending index of the search space.
  

Step 2: Calculate Two Midpoints

Instead of calculating a single midpoint (like Binary Search), Ternary Search computes two midpoints:

• mid1 → First one-third position of the current search space.
  
• mid2 → Second one-third position of the current search space.
  

Mathematically, these midpoints are calculated as:

mid1=low+(high−low)/3

mid2=high−(high−low)/3​

This divides the array into three parts.

Step 3: Compare the Target with mid1 and mid2

Once the two midpoints are determined, we compare the target element (key) with the elements at mid1 and mid2.

Case 1: Target matches arr[mid1]

• If arr[mid1] == key, return mid1 as the index where the key is found.
  

Case 2: Target matches arr[mid2]

• If arr[mid2] == key, return mid2 as the index where the key is found.
  

Case 3: Target is smaller than arr[mid1]

• If key < arr[mid1], this means the target must be in the leftmost section of the array.
  
• Update the search space to [low, mid1 - 1].
  

Case 4: Target is between arr[mid1] and arr[mid2]

• If arr[mid1] < key < arr[mid2], this means the target must be in the middle section.
  
• Update the search space to [mid1 + 1, mid2 - 1].
  

Case 5: Target is greater than arr[mid2]

• If key > arr[mid2], this means the target must be in the rightmost section of the array.
  
• Update the search space to [mid2 + 1, high].

Step 4: Repeat Until the Search Space is Exhausted

• The process is recursively or iteratively repeated until the search space is reduced to a single element.
  
• If low exceeds high, it means the element is not present in the array, so return -1.
  

For Example 

Let's take an example to understand this process in action. Consider the sorted array:

arr[] = {2, 4, 7, 10, 15, 19, 23, 29, 35}

We want to search for key = 19.

1. Initial search space → [low = 0, high = 8]

• Compute midpoints:
  • mid1=0+(8−0)/3=2
  • mid2=8−(8−0)/3=6
• arr[mid1] = arr[2] = 7
• arr[mid2] = arr[6] = 23

2. Comparison

• Since 7 < 19 < 23, search in the middle section [mid1 + 1, mid2 - 1] = [3, 5].

3. Next Iteration → [low = 3, high = 5]

• Compute new midpoints:
  • mid1=3+(5−3)/3=3
  • mid2=5−(5−3)/3=5
• arr[mid1] = arr[3] = 10
  
• arr[mid2] = arr[5] = 19
  

4. Match Found

• Since arr[mid2] == 19, return index 5.
  

Thus, key = 19 is found at index 5.

Implementation of Ternary Search in C++ 

Here’s a C++ implementation of Ternary Search using the recursive approach.

Code Example:

            #include 
using namespace std;

// Recursive Ternary Search Function
int ternarySearch(int arr[], int low, int high, int key) {
    if (low <= high) {
        // Calculate mid1 and mid2
        int mid1 = low + (high - low) / 3;
        int mid2 = high - (high - low) / 3;

        // Check if key is at mid1 or mid2
        if (arr[mid1] == key)
            return mid1; // Found at mid1
        if (arr[mid2] == key)
            return mid2; // Found at mid2

        // Search in the left part
        if (key < arr[mid1])
            return ternarySearch(arr, low, mid1 - 1, key);
        
        // Search in the right part
        else if (key > arr[mid2])
            return ternarySearch(arr, mid2 + 1, high, key);

        // Search in the middle part
        else
            return ternarySearch(arr, mid1 + 1, mid2 - 1, key);
    }

    return -1; // Key not found
}

int main() {
    int arr[] = {2, 4, 7, 10, 15, 19, 23, 29, 35};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 19;

    int index = ternarySearch(arr, 0, n - 1, key);

    if (index != -1)
        cout << "Element found at index " << index << endl;
    else
        cout << "Element not found" << endl;

    return 0;
}

          

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gUmVjdXJzaXZlIFRlcm5hcnkgU2VhcmNoIEZ1bmN0aW9uCmludCB0ZXJuYXJ5U2VhcmNoKGludCBhcnJbXSwgaW50IGxvdywgaW50IGhpZ2gsIGludCBrZXkpIHsKICAgIGlmIChsb3cgPD0gaGlnaCkgewogICAgICAgIC8vIENhbGN1bGF0ZSBtaWQxIGFuZCBtaWQyCiAgICAgICAgaW50IG1pZDEgPSBsb3cgKyAoaGlnaCAtIGxvdykgLyAzOwogICAgICAgIGludCBtaWQyID0gaGlnaCAtIChoaWdoIC0gbG93KSAvIDM7CgogICAgICAgIC8vIENoZWNrIGlmIGtleSBpcyBhdCBtaWQxIG9yIG1pZDIKICAgICAgICBpZiAoYXJyW21pZDFdID09IGtleSkKICAgICAgICAgICAgcmV0dXJuIG1pZDE7IC8vIEZvdW5kIGF0IG1pZDEKICAgICAgICBpZiAoYXJyW21pZDJdID09IGtleSkKICAgICAgICAgICAgcmV0dXJuIG1pZDI7IC8vIEZvdW5kIGF0IG1pZDIKCiAgICAgICAgLy8gU2VhcmNoIGluIHRoZSBsZWZ0IHBhcnQKICAgICAgICBpZiAoa2V5IDwgYXJyW21pZDFdKQogICAgICAgICAgICByZXR1cm4gdGVybmFyeVNlYXJjaChhcnIsIGxvdywgbWlkMSAtIDEsIGtleSk7CiAgICAgICAgCiAgICAgICAgLy8gU2VhcmNoIGluIHRoZSByaWdodCBwYXJ0CiAgICAgICAgZWxzZSBpZiAoa2V5ID4gYXJyW21pZDJdKQogICAgICAgICAgICByZXR1cm4gdGVybmFyeVNlYXJjaChhcnIsIG1pZDIgKyAxLCBoaWdoLCBrZXkpOwoKICAgICAgICAvLyBTZWFyY2ggaW4gdGhlIG1pZGRsZSBwYXJ0CiAgICAgICAgZWxzZQogICAgICAgICAgICByZXR1cm4gdGVybmFyeVNlYXJjaChhcnIsIG1pZDEgKyAxLCBtaWQyIC0gMSwga2V5KTsKICAgIH0KCiAgICByZXR1cm4gLTE7IC8vIEtleSBub3QgZm91bmQKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgYXJyW10gPSB7MiwgNCwgNywgMTAsIDE1LCAxOSwgMjMsIDI5LCAzNX07CiAgICBpbnQgbiA9IHNpemVvZihhcnIpIC8gc2l6ZW9mKGFyclswXSk7CiAgICBpbnQga2V5ID0gMTk7CgogICAgaW50IGluZGV4ID0gdGVybmFyeVNlYXJjaChhcnIsIDAsIG4gLSAxLCBrZXkpOwoKICAgIGlmIChpbmRleCAhPSAtMSkKICAgICAgICBjb3V0IDw8ICJFbGVtZW50IGZvdW5kIGF0IGluZGV4ICIgPDwgaW5kZXggPDwgZW5kbDsKICAgIGVsc2UKICAgICAgICBjb3V0IDw8ICJFbGVtZW50IG5vdCBmb3VuZCIgPDwgZW5kbDsKCiAgICByZXR1cm4gMDsKfQo=

Output: 

Element found at index 5

Explanation:

In the above code example-

1. We include the <iostream> header to enable input-output operations and use using namespace std to avoid prefixing standard functions with std::.
2. The ternarySearch() function is implemented recursively to search for an element in a sorted array using the ternary search algorithm.
3. Instead of dividing the search space into two halves like binary search, we divide it into three parts by calculating two midpoints:
• mid1 = low + (high - low) / 3
• mid2 = high - (high - low) / 3
4. We first check if the key is present at either mid1 or mid2. If found, we return the corresponding index.
5. If the key is smaller than arr[mid1], we search in the left segment (low to mid1 - 1).
6. If the key is greater than arr[mid2], we search in the right segment (mid2 + 1 to high).
7. If the key lies between mid1 and mid2, we search in the middle segment (mid1 + 1 to mid2 - 1).
8. If the key is not found in any segment, we return -1.
9. In the main() function, we initialize a sorted array and determine its size using sizeof(arr) / sizeof(arr[0]).
10. We set a key (19) to search for and call ternarySearch with the full range (0 to n - 1).
11. The function returns the index if the element is found; otherwise, we print "Element not found".

Advantages Of Ternary Search In Data Structures

1. Efficient for Large Search Spaces: Ternary search reduces the search space more aggressively compared to binary search, making it suitable for specific scenarios like unimodal function optimization.
   
2. Logarithmic Time Complexity: Similar to Binary Search, it runs in O(log₃ N) time, which is significantly better than O(N) of linear search.
   
3. Useful in Unimodal Function Optimization: Ternary search is particularly useful when searching for the maximum or minimum in a unimodal function.
   
4. Can Be Applied Recursively and Iteratively: Works well in both recursive and iterative implementations, offering flexibility.

Disadvantages Of Ternary Search In Data Structures

1. Slower Compared to Binary Search: Although the theoretical time complexity is O(log₃ N), in practice, Binary Search (O(log₂ N)) is faster due to fewer comparisons per iteration.
   
2. More Comparisons Per Step: Unlike binary search (1 comparison per iteration), ternary search performs 2 comparisons in each step, which increases execution time in real-world scenarios.
   
3. Increased Code Complexity: The logic of dividing the array into three parts instead of two makes ternary search harder to implement and debug compared to binary search.
   
4. Limited Practical Use: Since binary search is generally more efficient and widely used, ternary search is rarely preferred except in specific optimization problems.

Applications Of Ternary Search In Data Structures

• Unimodal Function Optimization: Ternary search is used to find the maximum or minimum of a function that first increases and then decreases (or vice versa). This makes it ideal for solving optimization problems in mathematical and computational scenarios.
  
• Finding the Peak Element in a Mountain Array:In a bitonic array (one that increases and then decreases), ternary search efficiently identifies the peak element. For example, in the array [1, 3, 7, 12, 9, 5, 2], ternary search can quickly determine that 12 is the peak.
  
• Searching in a Sorted Array: Ternary search can be used as an alternative to binary search when searching for an element in a sorted array. However, since it involves two comparisons per iteration instead of one, binary search is generally preferred due to its efficiency in practice.
  
• Competitive Programming Optimization: Ternary search is widely used in competitive programming, especially in problems requiring the optimization of a function over a given range. It is particularly useful in finding the optimal speed, cost, or efficiency parameter in constraint-based scenarios.
  
• Resource Allocation Problems: It is useful in problems involving the optimal distribution of resources, such as workload balancing among workers or minimizing the maximum load in scheduling and allocation tasks.
  
• Computer Graphics and Image Processing: Ternary search is applied in curve fitting and interpolation to determine the best values for rendering smooth and visually accurate graphics, helping enhance the quality of rendered images.

Conclusion

Ternary search is a powerful searching and optimization technique that divides the search space into three parts, making it useful in specific scenarios. While it shares similarities with binary search, its real strength lies in solving unimodal function optimization problems, finding peak elements in bitonic arrays, and resource allocation tasks. However, due to its additional comparisons per iteration, binary search remains the preferred choice for general searching in sorted arrays.

In essence, ternary search shines in optimization-based problems rather than simple searching tasks. Understanding its working principle and applications helps in leveraging its advantages when dealing with complex computational challenges.

Frequently Asked Questions

Q. How does ternary search differ from binary search?

Ternary search and binary search both work on a sorted array and use a divide-and-conquer approach to reduce the search space. However, ternary search divides the array into three parts by choosing two midpoints instead of one, whereas binary search divides it into two parts with a single midpoint. In theory, ternary search has a complexity of O(log₃ N) compared to O(log₂ N) for binary search, but in practice, binary search is often faster due to fewer comparisons per iteration.

Q. When should ternary search be used instead of binary search?

Ternary search is particularly useful when dealing with unimodal functions, where a function first increases and then decreases (or vice versa). It is used for finding maximum or minimum values in such functions efficiently. While it can be applied to sorted arrays for searching, binary search is generally preferred due to its lower number of comparisons and better practical performance.

Q. What are the conditions required to apply ternary search?

Ternary search can only be applied under the following conditions:

• The array or function must be sorted in a particular order (ascending or descending).
  
• For optimization problems, the function should be unimodal, meaning it has a single peak (maximum) or valley (minimum).
  
• The problem should allow a divide-and-conquer approach, where the search space can be repeatedly reduced.

Q. Is ternary search always faster than binary search?

No, ternary search is not always faster. Although its theoretical time complexity O(log₃ N) is slightly better than binary search O(log₂ N), it requires two comparisons per iteration instead of one, which makes it slower in most practical cases. Binary search is more cache-friendly and widely optimized in modern computing architectures, making it the preferred choice for searching in sorted arrays.

Q. Can ternary search be implemented both recursively and iteratively?

Yes, ternary search can be implemented using both recursive and iterative approaches. The recursive method divides the search space and calls itself on the appropriate segment, while the iterative method eliminates unnecessary recursion overhead by using a loop. Both implementations follow the same logic but have different memory usage patterns, with recursion using additional function call stack space.

Suggested Reads: 

1. What Is Selection Sort Algorithm? Explained With Code Examples
2. Learn All About Bubble Sort Algorithm (With Code Examples)
3. Merge Sort Algorithm | Working, Applications & More (+Examples)
4. Quick Sort Algorithm | Working, Applications & More (+Examples)
5. Heap Sort Algorithm - Working And Applications (+ Code Examples)