## 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:

- Initialize the left and right pointers to the start and end indices of the array, respectively.
- 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.

- Calculate the two midpoints,
- 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.