Skip to main content

Ternary Search (Geeks for Geeks)

Ternary Search is a divide-and-conquer search algorithm used to find the position of a target value within a sorted array. It divides the array into three parts and determines which part the target value belongs to, reducing the search space by one third each time.

  1. Divide the array into three parts by calculating two midpoints.
  2. Compare the target value with the values at these midpoints.
  3. If the target value matches either midpoint, return the index.
  4. If the target value is less than the first midpoint, repeat the process on the left third.
  5. If the target value is greater than the first midpoint but less than the second midpoint, repeat the process on the middle third.
  6. If the target value is greater than the second midpoint, repeat the process on the right third.
  7. If the target value is not found, return -1.

How does Ternary Search work?

  • It calculates two midpoints to divide the array into three parts.
  • It compares the target value with the elements at the midpoints.
  • Based on the comparison, it reduces the search space to one of the three parts and repeats the process.

Problem Description

Given a sorted array and a target element, implement the Ternary Search algorithm to find the index of the target element in the array. If the element is not present, return -1.

Examples

Example 1: Input: list = [1, 2, 3, 4, 5, 6, 7, 8, 9] target = 5 Output: 4

Example 2: Input: list = [1, 2, 3, 4, 5, 6, 7, 8, 9] target = 10 Output: -1

Your task

Complete the function ternary_search() which takes two integers n, k and an array arr, as input parameters and returns an integer denoting the answer. Return -1 if the number is not found in the array. You don't have to print answers or take inputs.

Expected Time Complexity: O(log3n)O(\log_3 n) Expected Auxiliary Space: O(1)O(1)

Constraints

  • 1<=n<=1061 <= n <= 10^6
  • 1<=k<=1061 <= k <= 10^6
  • 1<=arr[i]<=1091 <= arr[i] <= 10^9

Implementation

Written by @ngmuraqrdd
  def ternary_search(arr, target):
left, right = 0, len(arr) - 1

while left <= right:
mid1 = left + (right - left) // 3
mid2 = right - (right - left) // 3

if arr[mid1] == target:
return mid1
if arr[mid2] == target:
return mid2

if target < arr[mid1]:
right = mid1 - 1
elif target > arr[mid2]:
left = mid2 + 1
else:
left = mid1 + 1
right = mid2 - 1

return -1

Complexity Analysis

  • Time Complexity: O(log3n)O(\log_3 n), where nn is the number of elements in the array. The search space is divided into three parts each time, leading to a logarithmic time complexity base 3.
  • Space Complexity: O(1)O(1), as no extra space is required apart from the input array.

Advantages and Disadvantages

Advantages:

  • Faster than binary search for large arrays due to reducing the search space by one third each time.
  • Efficient for large datasets.

Disadvantages:

  • Requires the array to be sorted.
  • More complex to implement compared to binary search.
  • Not significantly faster than binary search for small datasets.

References