算法分析与设计

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