首页 > 代码库 > 动态法

动态法

1)二分查找法

可以看出非组合的尾递归,可以用循环来取代。

template<typename T>
int centerFind(const vector<T>& source,const T& finder)
{
    int ret=-2;
    int startIndex=0;
    int endIndex=source.size()-1;
    int CenterIndex=startIndex+(endIndex-startIndex)/2;

    while(ret==-2)
    {
        if(CenterIndex==startIndex&&startIndex==endIndex)//1个数
        {
            if(source[CenterIndex]==finder)
            {
                ret=CenterIndex;
            }
            else
            {
                ret=-1;
            }
        }
        else
        {
            if(source[CenterIndex]==finder)
            {
                ret=CenterIndex;
            }
            else if(source[CenterIndex]>finder)
            {
                endIndex=CenterIndex-1;
                CenterIndex=startIndex+(endIndex-startIndex)/2;
                if(startIndex>endIndex)
                {
                    ret=-2;
                }
            }
            else
            {
                startIndex=CenterIndex+1;
                CenterIndex=startIndex+(endIndex-startIndex)/2;
                if(startIndex>endIndex)
                {
                    ret=-2;
                }
            }
        }
    }
}

 

动态法