我正在尝试获取此算法的时间复杂性，但我不确定如何。会很高兴任何帮助。
`int g(int arr[], int start, int end, int k)
{
if (start > end) return 0;
int mid = (start + end) / 2;
if (arr[mid] < k) return 1 + g(arr, mid + 2, end, k);
if (arr[mid] > k) return 1 + g(arr, start, mid - 1, k);
return g(arr, start, mid - 1, k) + 1 +
g(arr, mid + 1, end, k);
}`
答案是o（n）。
这是使用二进制搜索机制的递归。每次我们检查arr[mid]是否等于值k；如果它小于k，则我们搜索数组的右半（mid+2应该是mid+1），如果更多，则我们搜索数组的左半部分，如果它等于k大批。因此，每次调用递归函数时，我们只使用一半的输入（一半的数组）。因此，我们可以写这样的东西：
t（n）= 2*t（n/2） 1
t（n）= 2*2*t（n/（2*2）） 1 1
...继续扩展
t（n）= 2^k*t（n/（2^k）） k
n/（2^k）= 2 ==> k = log（n）
t（n）= 2^（log（n））*1 log（n）=
O(n)知道2^log（n）= n使用日志规则。
即使您没有询问，但是空间复杂性将是O(log(n))，因为递归树的最大深度将是log（n）。