設(shè)有N個(gè)互不同的整數(shù)，按遞增順序存放在數(shù)組a[0..n-1]中，若存在一個(gè)下標(biāo)i（0《i<n）,使得a[i]=i.設(shè)計(jì)一個(gè)算法以O(shè)(log2n)時(shí)間找到這個(gè)下標(biāo)i
1 回答
慕仔3118017
TA貢獻(xiàn)16條經(jīng)驗(yàn) 獲得超5個(gè)贊
int i =0,j=n-1;
res =-1;
while(i<j)
{
????l=(j-i)/2+i;
????if (a[l]==l)
????{
????????res=l;break;
????}
????else if(a[l]<l)
????{
????????i=l;continue;
????}
????else if (a[l]>l)
????{
????????j=l;continue;
????}
}
用二分法查找，如果a[l]<l說明在a[l]右側(cè)才可能出現(xiàn)a[k]=k,同理a[l]>l說明要找的應(yīng)該在左側(cè)
-
qq_慕UI8003619。。。 -
慕勒7090901你這個(gè)如果是做后一個(gè)數(shù)的話，他是找不到的
- 1 回答
- 0 關(guān)注
- 2658 瀏覽
添加回答
舉報(bào)
0/150
提交
取消