二分探索再帰と非再帰C言語実現

1018 ワード

アルゴリズム面接試験 C

プログラマーの90%が正確に二分検索を書くことができないそうですが、試してみるとやはり注意すべき点が多いので、復習のために再帰と非再帰の書き方をメモしておきます

int binary_search(int array[],int n,int key)  //   
{
    int low=0;
    int high=n-1;
    while(low<=high)    //   =
    {
        if(array[low+(high-low)/2]==key)
        {
            return low+(high-low)/2;   //    low+
        }
        else if(array[low+(high-low)/2]>key)
        {
            high=low+(high-low)/2 -1;    //   -1
        }
        else
        {
            low=low+(high-low)/2 +1 ;  //   +1
        }
    }
    return -1;
}

int binary_search(int array[],int low,int high,int key)  //   ,     low high
{
    if(low<=high)
    {
        if(key==array[low+(high-low)/2])
            return (low+(high-low)/2);
        else if(key>array[low+(high-low)/2])
            return binary_search(array,low+(high-low)/2+1,high,key);
        else
            return binary_search(array,low,low+(high-low)/2-1,key);
    }
    else
    {
        return -1;
    }
}

Cookieとweb Storage

Nodeに基づいてwebsocketを用いてデータプッシュを行う.