K******g
发帖数: 1870 | 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*****Z
发帖数: 723 | 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*c
发帖数: 904 | 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*******b
发帖数: 1001 | 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;
|
|
