三分搜索算法的做法是：它先将待查元素x与n/3处的元素比较，然后将x与2n/3处的元素进行比较。比较的结果或者找到x，或者将搜索范围缩小的原来的n/3
1）编写C++程序实践算法
2）分析算法的时间复杂度
1）
#include <cstdio>int a[1000], n;bool flag;int T_search(int l, int r, int x){if(l <= r){int mid1 = l + (r - l) / 3;int mid2 = l + (r - l) * 2 / 3;if(a[mid2] < x)return T_search(mid2 + 1, r, x);else if(a[mid1] < x && a[mid2] > x)return T_search(mid1 + 1, mid2 - 1, x);else if(a[mid1] > x)return T_search(l, mid1 - 1, x);else if(a[mid1] == x)return mid1;else if(a[mid2] == x)return mid2;}return -1;}int main(){int x;flag = false;scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);scanf("%d", &x);if(T_search(0, n - 1, x) != -1)printf("Find\n");elseprintf("Not Find\n");}
2）
时间复杂度： O(3log3(n))
