输出二进制搜索算法的搜索次数有问题

Question

我一直在尝试获取在二进制搜索算法中完成的搜索次数。目标是根据算法中输入的数据量来测试执行了多少搜索。相关程序

//CBinarysearch.c//
#include <stdio.h>
#include <time.h>

#define NUM 100
#define MAX 200

int binary_s(int a[], int n, int s) {
    int lo, hi, mid;
    int c = 0;
    
    lo = 0;//loの初期化
    hi = n-1;//hiの初期化
    while (lo <= hi) {
        mid = (lo + hi) / 2;//midの初期化
        c++;
        if (s == a[mid]) break;//探索値がmidと同じ値となればloopを終了
        if (s > a[mid])//探索値がmidより大きい場合
            lo = mid + 1;//loの値を；１してmidへ移動
        else//探索値がmidより小さい場合
            hi = mid - 1;//hiの値をー１してmidへ移動
    }
    if (lo <= hi)
        printf("The numerical value %d is in array %d (array element %d)\n", s, mid+1, mid);
    else
        printf("Could not be located.\n");
    return c;
}

void shuffle(int a[]) {
    unsigned int i, j;
    int tmp;
    i = MAX - 1;
    while (i > 0) {//シャッフルのためのLoop
        j = rand() % (i + 1);//jの値をランダム化
        tmp = a[j];
        a[j] = a[i];
        a[i] = tmp;
        i--;
    }
}

int quicksort(int a[], int first, int last) {
    int i, j, temp, x;
    
    i = first;
    j = last;
    x = (a[i] + a[j]) / 2;//基準値は平均
    
    while (1) {
        while (a[i] < x) i++;
        while (a[j] > x) j--;
        //iがjより大きくなればwhile loopが解除される
        if (i >= j) break;
        //a[i]とa[j]を入れ替える
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        i++;
        j--;
    }
    if (first < i-1) quicksort(a, first, i-1);
    if (j + 1 < last) quicksort(a, j + 1, last);
    return 0;
}

int main(void) {
    int a[NUM];
    int i;
    int count;
    int s;
    srand((unsigned int)time(NULL));
    i = rand() % NUM;
    s = a[i];
    for (i = 0; i < NUM; i++) {//整列数列の作成
        a[i] = i + 1;
    }
    shuffle(a);//Fisher-Yates shuffle
    quicksort(a, 0, NUM-1);//クイックソートの呼び出し
    count = binary_s(a, NUM, s);
    printf("\n%d ", count);//交換回数の出力
    return 0;
}

我已经在这个领域待了很长时间了。在这一点上，我添加了更多细节只是为了使这个 post 可行。这很艰难。我可以寻求一些帮助吗？

Answer 1

您在初始化数组之前将 s 初始化为 s = a[i]; ：这具有未定义的行为。你应该改为写：

s = rand() % NUM + 1;

此外，shuffle 函数假设数组有 MAX 个元素，而您在 main() 中定义它的长度为 NUM。您应该将长度传递给 shuffle().

另请注意，如果数组中的值可以任意大，x = (a[i] + a[j]) / 2 将具有未定义的行为。

您还应该考虑在代码和注释之间添加一些白色 space 以使代码更具可读性，尤其是对于非日语读者。

这是修改后的版本：

//CBinarysearch.c// #include <stdio.h> #include <stdlib.h> #include <time.h> #define NUM 100 int binary_s(int a[], int n, int s) { int lo, hi, mid; int c = 0; lo = 0; // loの初期化 hi = n - 1; // hiの初期化 while (lo <= hi) { mid = lo + (hi - lo) / 2; // midの初期化 c++; if (s == a[mid]) // 探索€¤がmidと同じ€¤となればloopを終了 break; if (s > a[mid]) // 探索€¤がmidより大きい場合 lo = mid + 1; // loの€¤を；１してmidへ移動 else // 探索€¤がmidより小さい場合 hi = mid - 1; // hiの€¤をー１してmidへ移動 } if (lo <= hi) { printf("The numerical value %d is in array at index %d\n", s, lo); } else { printf("value %d Could not be located in array.\n", s); } return c; } void shuffle(int a[], int len) { int i, j; int tmp; for (i = len - 1; i > 0; i--) { // シャッフルのためのLoop j = rand() % (i + 1); // jの€¤をラン€ム化 tmp = a[j]; a[j] = a[i]; a[i] = tmp; } } void quicksort(int a[], int first, int last) { int i, j, temp, x; if (first >= last) return; i = first; j = last; x = ((long long)a[i] + a[j]) / 2; // 基準€¤は平均 while (1) { while (a[i] < x) i++; while (a[j] > x) j--; //iがjより大きくなればwhile loopが解除される if (i >= j) break; //a[i]とa[j]を入れ替える temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } quicksort(a, first, i - 1); quicksort(a, j + 1, last); } int main(void) { int a[NUM]; int i; int count; int s; srand((unsigned int)time(NULL)); for (i = 0; i < NUM; i++) { // 整列数列の作成 a[i] = i + 1; } s = a[rand() % NUM]; shuffle(a, NUM); // Fisher-Yates shuffle quicksort(a, 0, NUM - 1); // クイックソートの呼び出し count = binary_s(a, NUM, s); printf("iterations: %d\n", count); // 交換回数の出力 return 0; }

输出二进制搜索算法的搜索次数有问题

Having issues with outputting the number of searches of a Binary search algorithm

c