0

44ページのこのようなコード。



int binsearch(int x, int v[], int n)
{
    int low, high, mid;

    low = 0;
    high = n - 1;
    while(low <= high){
        mid = (high+low)/2;
        if(x < v[mid]){
            high = mid + 1;
        }else if(x > v[mid]){
            low = mid + 1;
        }else{
            return mid;
        }
        printf("mid is %d\n",mid);
    }

    return -1;
}

int main(void)
{
    int v[] = {2,3,4,7,8,23,54,65,76};
    int ret = binsearch(7, v, sizeof(v)/sizeof(int));

    printf("%d,ret is %d\n", sizeof(v),ret);
    return 0;
}

コンパイルして実行すると、結果としてデッドループになります! したがって、「low = mid + 1;」という行 「low = mid;」と取るべきですよね？thx.

4

1 に答える 1

6

あなたが投稿したコードの問題は の値ではありませんが、 の値lowの設定のテストではhigh...xが より小さい場合v[mid]、 の新しいインデックス値はhighよりも 1 小さく、大きくはなりませんmid。したがって、次のように変更します。

if(x < v[mid]){
    high = mid + 1;

に：

if(x < v[mid]){
    high = mid - 1;

ここで実際の例を見ることができます: http://ideone.com/E6Ma8

于 2012-09-28T16:55:51.777 に答える