設有N個互不同的整數，按遞增順序存放在數組a[0..n-1]中，若存在一個下標i（0《i<n）,使得a[i]=i.設計一個算法以O(log2n)時間找到這個下標i
1 回答
慕仔3118017
TA貢獻16條經驗 獲得超5個贊
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]右側才可能出現a[k]=k,同理a[l]>l說明要找的應該在左側
-
qq_慕UI8003619。。。 -
慕勒7090901你這個如果是做后一個數的話，他是找不到的
- 1 回答
- 0 關注
- 2646 瀏覽
添加回答
舉報
0/150
提交
取消