假设数组a中的数据按升序排列，请用Ｃ语言写出在数组a中查找元素x的折半查找递归算法，算法名称为BinarySearch(int a[], int x, int left, int right)．并给出其时间复杂度T(n)的递推公式，计算其时间复杂度。

BinarySearch(int a[], int x, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (a[mid] == x) {
return mid;
} else if (a[mid] > x) {
return BinarySearch(a, x, left, mid - 1);
} else {
return BinarySearch(a, x, mid + 1, right);
}
}

时间复杂度T(n)的递推公式为：T(n) = T(n/2) + O(1)，其中n为数组a的长度。根据主定理，可以得到T(n) = O(log n)。