算法分析与设计

Question

设有N个互不同的整数，按递增顺序存放在数组a[0..n-1]中，若存在一个下标i（0《i<n）,使得a[i]=i.设计一个算法以O(log2n)时间找到这个下标i

Answer 1

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说明要找的应该在左侧