请教一个问题的答案，好像以前有人讨论过 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一个问题的答案，好像以前有人讨论过

请教一个问题的答案，好像以前有人讨论过# JobHunting - 待字闺中

K*g2010-06-05 07:06

1 楼

You have an array A of unknown length L. The array contains numbers that
are distinct and sorted ascendingly. The array is 1-indexed i.e. first
element is got by A[1] and not A[0]. To help u, since L is not known, when
an index out of bounds is used, then a special value of NOT_FOUND is
returned. The question is to find some positive integer n such that when
used as the index, the result from the array is the n itself. i.e. A[n] = n.

Z*Z2010-06-05 07:06

2 楼

【我是这样想的，对任意的i
如果A[i] == i，那么i就是要找的
如果A[i] > i或者A[i]==NOT_FOUND, 那么这样的数只能是在i之前
如果A[i] < i，那么这个解应该在i之后（如果存在的话）
找一个k，使得这个解在2^k和2^(k+1)之间，然后二分查找
在 KingMing (洱东金茗) 的大作中提到: 】
n.

y*c2010-06-05 07:06

3 楼

i=1;
while(A[i]!=Not_found&&A[i]<=i){
if(A[i]==i)
return i;
i *= 2;
}
if(A[i]>i)
return -1;
// then binary search in [i/2, i]
int lb=i/2, ub=i;
while(lb+1!=ub){
m = lb/2 + ub/2;
if(x[m] < m)
lb=m;
else
ub = m;
}
if(A[m]!=Not_found&&A[m]==m)
return m;
else
return -1;

P*b2010-06-05 07:06

4 楼

这个code有问题

【在 y*c 的大作中提到】

: i=1;
: while(A[i]!=Not_found&&A[i]<=i){
: if(A[i]==i)
: return i;
: i *= 2;
: }
: if(A[i]>i)
: return -1;
: // then binary search in [i/2, i]
: int lb=i/2, ub=i;