Explain what is Ternary Search in C# ?

Ternary Search is a divide-and-conquer algorithm used to search for an element in a sorted array. It is similar to binary search but divides the array into three parts instead of two.

The basic idea behind Ternary Search is to divide the input array into three parts and determine which part the target element might lie in. Then, recursively apply the search process to the selected part.

Here’s the general algorithm for Ternary Search:

  1. Initialize the left and right pointers to the start and end indices of the array, respectively.
  2. While the left pointer is less than or equal to the right pointer:
    • Calculate the two midpoints, mid1 and mid2, such that:
      • mid1 = left + (right - left) / 3
      • mid2 = right - (right - left) / 3
    • If the target element is equal to arr[mid1] or arr[mid2], return the index of the target element.
    • If the target element is less than arr[mid1], update the right pointer to mid1 - 1 and repeat the search process in the first part.
    • If the target element is greater than arr[mid2], update the left pointer to mid2 + 1 and repeat the search process in the third part.
    • If the target element is between arr[mid1] and arr[mid2], update the left pointer to mid1 + 1 and the right pointer to mid2 - 1 and repeat the search process in the second part.
  3. If the loop terminates without finding the target element, it does not exist in the array.

Here’s an example implementation of the Ternary Search algorithm in C#:

public static int TernarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid1 = left + (right - left) / 3;
        int mid2 = right - (right - left) / 3;

        if (arr[mid1] == target)
            return mid1;

        if (arr[mid2] == target)
            return mid2;

        if (target < arr[mid1])
            right = mid1 - 1;
        else if (target > arr[mid2])
            left = mid2 + 1;
        else
        {
            left = mid1 + 1;
            right = mid2 - 1;
        }
    }

    return -1; // Target element not found
}

You can use the TernarySearch() method to search for a target element in a sorted array. For example:

int[] arr = { 2, 5, 8, 10, 13, 18, 21, 25 };
int target = 13;

int index = TernarySearch(arr, target);

Console.WriteLine($"The target element {target} is found at index {index}.");

In this example, the target element 13 is searched in the sorted array arr using the Ternary Search algorithm, and the index of the target element is displayed in the console.

Ternary Search is an efficient algorithm for searching in sorted arrays. It has a time complexity of O(log3 N), where N is the number of elements in the array.

error: Content is protected !!