I'm stuck with trying to get the number of searches done within a Binary search algorithm. The goal is to test how many searches are done depending on how much data is put into the algorithm. The program in 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;
}

I've been at this for an embarrassingly long time. And at this point I am adding more details just to make this post viable. It's been rough. May I ask for some help, please?

CodePudding user response：

You intialize s as s = a[i]; before initializing the array: this has undefined behavior. You should instead write:

s = rand() % NUM   1;

Furthermore the shuffle function assumes the array has MAX elements whereas you define it with a length of NUM in main(). You should pass the length to shuffle().

Also note that x = (a[i] a[j]) / 2 would have undefined behavior if the values in the array can be arbitrary large.

You should also consider adding some white space between the code and the comments to make the code more readable, especially to non Japanese readers.

Here is a modified version:

//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;
}