#每日一面BAT#第15题 a[x] == x


在一个严格单调递增的整数数组中找到a[x] == x的位置?
已邀请:

EagleSky - 每天刷刷算法多好,真不想做学术

赞同来自: 天天 csryan scordw


设整数\(x_1 > x_2\),并且有\(x_1 = x_2 + d\)。由于数组\(a\)是一个严格单调递增的整数数组,所以必然有\(a[x_1] \geqslant a[x_2] + d\)。
两边同时减去\(x_1\),即\(a[x_1] - x_1 \geqslant a[x_2] + d - x_2 -d = a[x_2] - x_2\)。所以\(f(x) = a[x] - x\) 也是一个单调递增的函数。
那么原问题寻找\(a[x] = x\)的位置也就变成了查找单调递增函数\(f(x) = 0\)时对应的\(x\)。这样就可以直接使用二分查找来做了,时间复杂度为\(O(\log{n})\)
void find(int a[], int l, int r)
{
  if (l > r)
    return -1;
  int k = (l + r) / 2;
  if (a[k] == k)
    return k;
  else if (a[k] > k)
    return find(a, l, k - 1);
  else
    return find(a, k + 1, r);
}

要回复问题请先登录注册

返回顶部