Ternary search algorithm in C#

Ternary search is a searching algorithm that efficiently finds the position of a target value within a sorted collection. It operates by dividing the search space into three parts and recursively narrowing down the search range.

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
        int target = 23;

        int index = TernarySearch(arr, target);

        if (index != -1)
        {
            Console.WriteLine($"Element {target} found at index {index}");
        }
        else
        {
            Console.WriteLine("Element not found");
        }
    }

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

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

            if (arr[mid1] == target)
            {
                return mid1; // Element found at mid1
            }
            if (arr[mid2] == target)
            {
                return mid2; // Element found at mid2
            }
            if (target < arr[mid1])
            {
                right = mid1 - 1; // Target is in the left partition
            }
            else if (target > arr[mid2])
            {
                left = mid2 + 1; // Target is in the right partition
            }
            else
            {
                left = mid1 + 1;
                right = mid2 - 1; // Target is in the middle partition
            }
        }

        return -1; // Element not found
    }
}

Let's break down the steps of ternary search using this example:

1. We have a sorted array 'arr' containing elements in ascending order ('arr = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 }') and a target value that we want to find ('target = 23').
2. We initialize two pointers, 'left' and 'right', which represent the leftmost and rightmost indices of the current search range. In this case, 'left = 0' and 'right = arr.Length - 1 = 9'.
3. The algorithm divides the search space into three parts by calculating two midpoints, 'mid1' and 'mid2', as follows:
   'partitionSize = (right - left) / 3'
   'mid1 = left + partitionSize'
   'mid2 = right - partitionSize'
4. The algorithm compares the values at 'mid1' and 'mid2' with the target value. If either of them is equal to the target, it means the target element is found, and the algorithm returns the respective index.
5. If the target is less than the value at 'mid1', the algorithm narrows down the search range to the left partition (from left to 'mid1 - 1').
6. If the target is greater than the value at 'mid2', the algorithm narrows down the search range to the right partition ('from mid2 + 1 to right').
7. If the target is not found in either of the above cases, it lies within the middle partition. The algorithm updates left to 'mid1 + 1' and right to 'mid2 - 1', effectively narrowing down the search range to the middle partition.
8. The algorithm repeats steps 3 to 7 until either the target element is found or the search range is exhausted ('left > right'). If the search range is exhausted, it means the target element is not present in the array, and the algorithm returns -1.

In this example, the ternary search algorithm determines that the target value 23 is located at index 5 in the array ('arr[5]'). The program outputs: "Element 23 found at index 5".

Ternary search efficiently narrows down the search space by dividing it into three parts at each step. It performs well for uniformly distributed and sorted data. However, it may exhibit poor performance for non-uniformly distributed data or when the data is not sorted.