2写一个三分检索程序,首先检查n/3的元素是否等于某个x的值,然后检查2n/3处的元素,这样,或者找到或者把集合缩小到原来的1/3.找到输出元素下标,否则输出-1

以下是一个简单的三分检索程序的实现，输入参数为待查找的数组a，数组长度n，以及要查找的元素x。程序首先检查n/3和2n/3处的元素，如果其中任意一个等于x，则返回对应的下标；否则，如果n<=3，则返回-1；否则，如果这两个元素都大于x，则在a[0]到a[n/3-1]范围内继续查找；如果这两个元素都小于x，则在a[2n/3]到a[n-1]范围内继续查找；否则，在a[n/3]到a[2n/3]范围内继续查找。具体实现如下：

int ternary_search(int a[], int n, int x) {
    int left = 0, right = n-1;
    while (left <= right) {
        int one_third = left + (right - left) / 3;
        int two_third = left + 2 * (right - left) / 3;
        if (a[one_third] == x) {
            return one_third;
        } else if (a[two_third] == x) {
            return two_third;
        } else if (x < a[one_third]) {
            right = one_third - 1;
        } else if (x > a[two_third]) {
            left = two_third + 1;
        } else {
            left = one_third + 1;
            right = two_third - 1;
        }
    }
    return -1;
}

该程序的时间复杂度为O(log3(n))。