三分查找算法在非有序数组中的D语言实现

在非有序数组中使用三分查找查找某个元素，可以按照以下步骤进行D语言实现：

1. 定义一个函数 ternary_search(arr: T[], left: int, right: int, target: T): int，其中 arr 是非有序数组，left 是数组的左边界，right 是数组的右边界，target 是要查找的元素。

2. 在函数内部，首先判断 left 是否大于 right，如果是，则返回 -1 表示未找到。

3. 计算两个划分点 mid1 和 mid2，将数组划分为三个部分。

   • mid1 = left + (right - left) / 3
   • mid2 = right - (right - left) / 3

4. 分别判断 arr[mid1] 和 arr[mid2] 是否等于 target，如果等于则返回 mid1 或 mid2。

5. 如果 arr[mid1] 大于 target，则在左侧部分进行递归查找，即调用 ternary_search(arr, left, mid1 - 1, target)。

6. 如果 arr[mid2] 小于 target，则在右侧部分进行递归查找，即调用 ternary_search(arr, mid2 + 1, right, target)。

7. 如果 arr[mid1] 小于等于 target 且 arr[mid2] 大于等于 target，则在中间部分进行递归查找，即调用 ternary_search(arr, mid1 + 1, mid2 - 1, target)。

8. 如果以上条件都不满足，则返回 -1 表示未找到。

以下是完整的D语言实现：

import std.stdio;

int ternary_search(T)(T[] arr, int left, int right, T target)
{
    if (left > right)
        return -1;

    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 (arr[mid1] > target)
        return ternary_search(arr, left, mid1 - 1, target);
    if (arr[mid2] < target)
        return ternary_search(arr, mid2 + 1, right, target);

    return ternary_search(arr, mid1 + 1, mid2 - 1, target);
}

void main()
{
    int[] arr = [1, 5, 8, 12, 15, 18, 22, 26, 28, 31];
    int target = 18;
    int index = ternary_search(arr, 0, arr.length - 1, target);

    if (index != -1)
        writeln('Element found at index ', index);
    else
        writeln('Element not found');
}

以上代码中，我们定义了一个非有序数组 arr，要查找的元素是 target。通过调用 ternary_search 函数，可以在非有序数组中使用三分查找来查找该元素。最后根据返回的索引结果判断是否找到了目标元素。