paizaラーニングレベルアップ問題集の指定要素の検索(query)をやってみました。

問題

実行時間制限超過コード

#include <stdio.h>

int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	int A[N];
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	for (int q = 0; q < Q; q++) {
		int k;
		scanf("%d", &k);
		for (int i = 0; i <= N; i++) {
			if (i == N) {
				puts("NO");
			} else if (A[i] == k) {
				puts("YES");
				break;
			}
		}
	}
	return 0;
}

とりあえずリファクタリング

とりあえず

配列部分をクラスのコンストラクタ引数に渡し
クエリ部分をメソッドの引数に渡す

ようにしたいと思います。

UIntArray.h

#ifndef UINTARRAY_H_
#define UINTARRAY_H_

#include <stddef.h>
#include <stdbool.h>

typedef struct __UIntArray _UIntArray;

typedef struct UIntArray {
	_UIntArray *_array;
	bool (*search)(const struct UIntArray*, unsigned);
} UIntArray;

UIntArray* new_UIntArray(size_t, const unsigned*);

void free_UIntArray(UIntArray**);

#endif /* UINTARRAY_H_ */

UIntArray.c

#include <stdlib.h>
#include <string.h>

#include "UIntArray.h"

struct __UIntArray {
	size_t n;
	unsigned a[];
};

static bool UIntArray_search(const UIntArray *uIntArray, unsigned k) {
	for (size_t i = 0; i < uIntArray->_array->n; i++)
		if (uIntArray->_array->a[i] == k)
			return true;
	return false;
}

UIntArray* new_UIntArray(size_t n, const unsigned *a) {
	UIntArray *uIntArray = (UIntArray*) malloc(sizeof(UIntArray));
	if (!uIntArray)
		return NULL;
	uIntArray->_array = (_UIntArray*) malloc(sizeof(_UIntArray) + sizeof(uIntArray->_array->a[0]) * n);
	if (!uIntArray->_array) {
		free(uIntArray);
		return NULL;
	}
	uIntArray->_array->n = n;
	memcpy(uIntArray->_array->a, a, sizeof(uIntArray->_array->a[0]) * n);
	uIntArray->search = UIntArray_search;
	return uIntArray;
}

void free_UIntArray(UIntArray** uIntArray) {
	free((*uIntArray)->_array);
	(*uIntArray)->_array = NULL;
	free(*uIntArray);
	*uIntArray = NULL;
}

実行時間計測

ここで、$N=100000$, $Q=100000$の場合の実行時間を計測したいと思います。
※全部NOを出力するのが最も時間かかります。

main.c

#include <stdio.h>
#include "UIntArray.h"
#ifndef NDEBUG
#include <assert.h>
#include <time.h>
#endif

int main() {
	size_t N, Q;
#ifdef NDEBUG
	scanf("%zu %zu", &N, &Q);
	unsigned A[N];
	for (size_t i = 0; i < N; i++) {
		scanf("%u", &A[i]);
	}
#else
	clock_t start = clock();
	N = 100000;
	unsigned A[N];
	for (size_t i = 0; i < N; i++) {
		A[i] = i * 10 + i / 9091;
	}
	Q = 100000;
	unsigned j = 99998;
	unsigned k = 1000000;
#endif
	UIntArray *uIntArray = new_UIntArray(N, A);
	while (Q--) {
#ifdef NDEBUG
		unsigned k;
		scanf("%u", &k);
#else
		k -= 1;
		if (k == j * 10 + j / 9091) {
			j -= 1;
			k -= 1;
		}
#endif
		puts(uIntArray->search(uIntArray, k) ? "YES" : "NO");
	}
	free_UIntArray(&uIntArray);
#ifndef NDEBUG
	fprintf(stderr, "took %f sec.\n", (double) (clock() - start) / CLOCKS_PER_SEC);
#endif
	return 0;
}

手元のWindows環境で、以下のバッチファイルを作成して実行しました。

main.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 main.c UIntArray.c -o main 1>main.txt 2>&1
if exist main.exe (
	.\main
	echo %ERRORLEVEL%
	del main.exe
	del main.txt
) else (
	type main.txt
)
pause

10回実行した結果、平均24.1866秒かかりました。

計算量を意識する

先述の例では、検索の部分で

$j=1,2,\dots,Q$について
- $i=1,2,\dots,N$について
  - $\dots$

という二重ループになっており、計算量は$NQ$に比例します（これをランダウの記号では$O(NQ)$と表現されます）。$O$の中身$NQ$が最大で$10^{10}$になってしまいますが、これを何とか$10^7$に押さえたいです。

例えば、

要素数1000001の真偽値配列$B=\left(b_j\right)_{0\le i\le 1000000}$を用意し、全要素falseで初期化する
$i=1,2,\dots,N$に対し、$B_{A_i}$をtrueにする
整数$k$に対して$b_k=\text{true}$ならばYESを、$b_k=\text{false}$ならばNOを出力する

ようにすれば、クエリ1回（1回の検索）について$O(1)$の計算量になり、$Q$回の検索では$O(Q)$の計算量になります。最初のtrue設定と合わせて、全体の計算量は$O(N+Q)$となります。

Bucket.h

#ifndef BUCKET_H_
#define BUCKET_H_

#include <stddef.h>
#include <stdbool.h>

typedef struct __Bucket _Bucket;

typedef struct Bucket {
	_Bucket *_bucket;
	bool (*search)(const struct Bucket*, unsigned);
} Bucket;

Bucket* new_Bucket(size_t, const unsigned*);

void free_Bucket(Bucket**);

#endif /* BUCKET_H_ */

Bucket.c

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "Bucket.h"

static unsigned maximum(size_t n, const unsigned *A) {
	if (!n || !A) return 0;
	unsigned max = A[0];
	for (size_t i = 1; i < n; i++)
		if (A[i] > max)
			max = A[i];
	return max;
}

struct __Bucket {
	unsigned max;
	bool bucket[];
};

static bool Bucket_search(const Bucket *bucket, unsigned k) {
	if (bucket->_bucket->max < k) {
		return false;
	}
	return bucket->_bucket->bucket[k];
}

Bucket* new_Bucket(size_t n, const unsigned *a) {
	unsigned max = maximum(n, a);
	Bucket *bucket = (Bucket*) malloc(sizeof(Bucket));
	if (!bucket)
		return NULL;
	bucket->_bucket = (_Bucket*) malloc(sizeof(_Bucket) + sizeof(bucket->_bucket->bucket[0]) * (max + 1));
	if (!(bucket->_bucket)) {
		free(bucket);
		return NULL;
	}
	bucket->_bucket->max = max;
	memset(bucket->_bucket->bucket, false, sizeof(bucket->_bucket->bucket[0]) * (max + 1));
	for (size_t i = 0; i < n; i++) {
		bucket->_bucket->bucket[a[i]] = true;
	}
	bucket->search = Bucket_search;
	return bucket;
}

void free_Bucket(Bucket **bucket) {
	free((*bucket)->_bucket);
	(*bucket)->_bucket = NULL;
	free(*bucket);
	*bucket = NULL;
}

main関数は、UIntArrayを使っていた部分をBucketに変えるだけです。
※入力配列に1000000を含む場合が最もメモリを使います。

main.c

#include <stdio.h>
#include "Bucket.h"
#ifndef NDEBUG
#include <assert.h>
#include <time.h>
#endif

int main() {
	size_t N, Q;
#ifdef NDEBUG
	scanf("%zu %zu", &N, &Q);
	unsigned A[N];
	for (size_t i = 0; i < N; i++) {
		scanf("%u", &A[i]);
	}
#else
	clock_t start = clock();
	N = 100000;
	unsigned A[N];
	for (size_t i = 0; i < N; i++) {
		A[i] = i * 10 + i / 9091;
	}
	Q = 100000;
	unsigned j = 99998;
	unsigned k = 1000000;
#endif
	Bucket *bucket = new_Bucket(N, A);
	while (Q--) {
#ifdef NDEBUG
		unsigned k;
		scanf("%u", &k);
#else
		k -= 1;
		if (k == j * 10 + j / 9091) {
			j -= 1;
			k -= 1;
		}
#endif
		puts(bucket->search(bucket, k) ? "YES" : "NO");
	}
	free_Bucket(&bucket);
#ifndef NDEBUG
	fprintf(stderr, "took %f sec.\n", (double) (clock() - start) / CLOCKS_PER_SEC);
#endif
	return 0;
}

main.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 main.c Bucket.c -o main 1>main.txt 2>&1
if exist main.exe (
	.\main
	echo %ERRORLEVEL%
	del main.exe
	del main.txt
) else (
	type main.txt
)
pause

手元のWindows環境で10回実行したところ、平均6.9442秒でした（あれ？）。

提出コード

複数ファイルで提出できませんので、一つにまとめます。

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	int A[N];
	int M = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
		if (A[i] > M)
			M = A[i];
	}
	bool B[++M];
	memset(B, false, sizeof(B));
	for (int i = 0; i < N; i++) {
		B[A[i]] = true;
	}
	for (int q = 0; q < Q; q++) {
		int k;
		scanf("%d", &k);
		puts(k < M && B[k] ? "YES" : "NO");
	}
	return 0;
}

提出結果：0.02秒以内に完了しました。

テストコード

先程、Bucketクラス（C言語には“クラス”は無いが）を定義しました。
Bucketクラスの

コンストラクタ
searchメソッド

について、テストコードを作成したいと思います。

コンストラクタのテスト

インスタンスが生成されているか
メンバ変数が設定されているか

をテストします。
インスタンスが生成されているかどうかは、今回想定される最大値1000000に対してメモリ不足にならないか、確かめます。
メンバ変数については、C言語の場合、未定義構造体へのポインタにアクセスして（privateな）値を取得することもできます。後述のコードではそのようにしていますが、「そんなこともできるんだ」程度でよいです。getterメソッドがあればそのテストで確認すればよいでしょう。
厳密にいえばC言語の場合は、メソッドも設定されているかテストする必要もありますが、それはメソッドのテストに譲ります。

検索メソッドのテスト

今回は、単に

trueを返す場合
falseを返す場合

だけでなく、要素の最大値を超えた検索対象が引数として渡された場合のテストもする必要があります。また、今回の問題では与えられませんが、要素数が0の配列に対しても忘れずテストしましょう。

今回は単体テストツールとしてminunit.hを使います。

BucketTest.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <time.h>
#include <errno.h>
#include "minunit.h"
#include "Bucket.h"

int tests_run = 0;

static char* message_b(size_t k, bool expected, bool actual) {
	static char msg[80];
	sprintf(msg, "[%zu] Error: expected: <%s> but was: <%s>", k,
		expected ? "true" : "false",
		actual ? "true" : "false"
	);
	return msg;
}

static char* message_u(unsigned expected, unsigned actual) {
	static char msg[80];
	sprintf(msg, "Error: expected: <%u> but was: <%u>", expected, actual);
	return msg;
}

static char* test_constructor(size_t n, unsigned *A, unsigned m, bool *expected) {
	Bucket *bucket = new_Bucket(n, A);
	mu_assert("Error: expected: <not null> but was: <null>", bucket);
	void* p = (void*) bucket->_bucket;
	unsigned max = *(unsigned*)p;
	bool actual[max+1];
	memcpy(actual, p + sizeof(unsigned), sizeof(actual));
	free_Bucket(&bucket);
	mu_assert(message_u(m, max), max == m);
	for (size_t i = 0; i <= (size_t) max; i++) {
		mu_assert(message_b(i, expected[i], actual[i]), expected[i] == actual[i]);
	}
	mu_assert("Error: expected: <null> but was: <not null>", !bucket);
	return 0;
}

static char* test_constructor_0() {
	bool B[] = {false};
	return test_constructor(0, NULL, 0, B);
}
static char* test_constructor_1() {
	unsigned A[] = {};
	bool B[] = {false};
	return test_constructor(sizeof(A) / sizeof(A[0]), A, 0, B);
}
static char* test_constructor_2() {
	unsigned A[] = {0};
	bool B[] = {true};
	return test_constructor(sizeof(A) / sizeof(A[0]), A, 0, B);
}
static char* test_constructor_3() {
	unsigned A[] = {1000000};
	bool B[1000001] = {};
	B[1000000] = true;
	return test_constructor(sizeof(A) / sizeof(A[0]), A, 1000000, B);
}

static char* test_search_true(unsigned k, size_t n, ...) {
	unsigned A[n];
	va_list args;
	va_start(args, n);
	for (size_t i = 0; i < n; i++) {
		A[i] = (unsigned) va_arg(args, unsigned);
	}
	va_end(args);
	Bucket *bucket = new_Bucket(n, A);
	bool result = bucket->search(bucket, k);
	free_Bucket(&bucket);
	mu_assert("Error: expected: <true> but was: <false>", result);
	return 0;
}

static char* test_search_false(unsigned k, size_t n, ...) {
	unsigned A[n];
	va_list args;
	va_start(args, n);
	for (size_t i = 0; i < n; i++) {
		A[i] = (unsigned) va_arg(args, unsigned);
	}
	va_end(args);
	Bucket *bucket = new_Bucket(n, A);
	bool result = bucket->search(bucket, k);
	free_Bucket(&bucket);
	mu_assert("Error: expected: <false> but was: <true>", !result);
	return 0;
}

static char* test_search_0() {
	Bucket *bucket = new_Bucket(0, NULL);
	bool result = bucket->search(bucket, 0);
	free_Bucket(&bucket);
	mu_assert("Error: expected: <false> but was: <true>", !result);
	return 0;
}

static char* test_search_1() {return test_search_false(0, 0);}
static char* test_search_2() {return test_search_true(0, 1, 0);}
static char* test_search_3() {return test_search_false(0, 1, 1);}
static char* test_search_4() {return test_search_true(1, 1, 1);}
static char* test_search_5() {return test_search_false(2, 1, 1);}
static char* test_search_6() {return test_search_true(1000000, 1, 1000000);}

static char* all_tests() {
	mu_run_test(test_constructor_0);
	mu_run_test(test_constructor_1);
	mu_run_test(test_constructor_2);
	mu_run_test(test_constructor_3);
	mu_run_test(test_search_0);
	mu_run_test(test_search_1);
	mu_run_test(test_search_2);
	mu_run_test(test_search_3);
	mu_run_test(test_search_4);
	mu_run_test(test_search_5);
	mu_run_test(test_search_6);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

Windows環境の場合、以下のようなバッチファイルを作っておくとテストしやすいと思います。

BucketTest.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 BucketTest.c Bucket.c -o BucketTest 1>BucketTest.txt 2>&1
if exist BucketTest.exe (
	.\BucketTest
	echo %ERRORLEVEL%
	del BucketTest.exe
	del BucketTest.txt
) else (
	type BucketTest.txt
)
pause

入力チェック

範囲チェック

問題集や競技プログラミングでは制約条件通りの値が与えられますが、実務ではそうとは限りません。そこで、入力チェックを行う必要があります。
今回は

$1\le N\le 100000$
$1\le Q\le 100000$
$0\le A_i\le 1000000\ (i=1,2,\dots,N)$
$0\le K_j\le 1000000\ (j=1,2,\dots,Q)$
数列$A$に重複した要素は無い

ので、まずは「重複要素無し」以外の4条件を実装します。

input.h

#ifndef INPUT_H_
#define INPUT_H_

#include <stdbool.h>

bool read_size(const char*, size_t*, size_t*);

bool read_element(const char*, unsigned*);

#endif /* INPUT_H_ */

※以下のコードで、static関数は他プロジェクトからの使い回しであるものとします^^;　したがって、テストは省略させていただきます。

input.c

#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>
#include <inttypes.h>
#include <errno.h>
#include "input.h"

static bool is_positive_number(const char *s) {
	if (!(s && *s))
		return false;
	if (s[0] == '0')
		return strlen(s) == 1;
	for (const char *c = s; *c; c++)
		if (!isdigit(*c))
			return false;
	return true;
}

static bool parse_unsigned(const char *str, uintmax_t *n, uintmax_t max) {
	errno = 0;
	if (!is_positive_number(str)) {
		errno = EINVAL;
		return false;
	}
	char *s = NULL;
	*n = strtoumax(str, &s, 10);
	if (errno) {
		return false;
	} else if (s && *s) {
		errno = EINVAL;
		return false;
	} else if (*n > max) {
		errno = ERANGE;
		return false;
	}
	return true;
}

bool parse_uint(const char *str, unsigned *n) {
	uintmax_t m = 0;
	if (!parse_unsigned(str, &m, UINT_MAX)) {
		return false;
	}
	*n = (unsigned) m;
	return true;
}

bool parse_ulong(const char *str, size_t *n) {
	uintmax_t m = 0;
	if (!parse_unsigned(str, &m, SIZE_MAX)) {
		return false;
	}
	*n = (size_t) m;
	return true;
}

bool read_size(const char *str, size_t *n, size_t *q) {
	errno = 0;
	if (!str) {
		errno = EINVAL;
		return false;
	}
	char s[14];
	strncpy(s, str, sizeof(s));
	char *t = strtok(s, " ");
	if (!parse_ulong(t, n)) {
		return false;
	} else if (*n < 1 || 100000 < *n) {
		errno = ERANGE;
		return false;
	}
	t = strtok(NULL, " ");
	if (!parse_ulong(t, q)) {
		return false;
	} else if (*q < 1 || 100000 < *q) {
		errno = ERANGE;
		return false;
	}
	t = strtok(NULL, " ");
	if (t) {
		errno = EINVAL;
		return false;
	}
	return true;
}

bool read_element(const char *str, unsigned *k) {
	if (!parse_uint(str, k)) {
		return false;
	} else if (*k > 1000000) {
		errno = ERANGE;
		return false;
	}
	return true;
}

重複チェック

先程のBucketクラス（第一版）では検索の高速化を行いましたが、第二版では挿入メソッドを追加します。要素が重複した場合、挿入メソッドはfalseを返すようにします。

あくまで「入力チェック」なので、入力モジュールの責務とする設計方針もあります、というか、現場ではそうなるでしょう。

Bucket.h

#ifndef BUCKET_H_
#define BUCKET_H_

#include <stddef.h>
#include <stdbool.h>

typedef struct __Bucket _Bucket;

typedef struct Bucket {
	_Bucket *_bucket;
	bool (*insert)(struct Bucket*, unsigned);
	bool (*search)(const struct Bucket*, unsigned);
} Bucket;

Bucket* new_Bucket(void);

void free_Bucket(Bucket**);

#endif /* BUCKET_H_ */

Bucket.c

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "Bucket.h"

struct __Bucket {
	unsigned max;
	bool bucket[];
};

static bool Bucket_insert(Bucket *bucket, unsigned a) {
	if (a <= bucket->_bucket->max && bucket->_bucket->bucket[a]) {
		return false;
	}
	if (a > bucket->_bucket->max) {
		void* temp = realloc(bucket->_bucket, sizeof(_Bucket) + sizeof(bucket->_bucket->bucket[0]) * (a + 1));
		if (!temp) {
			free(bucket->_bucket);
			bucket->_bucket = NULL;
			return false;
		}
		bucket->_bucket = (_Bucket*) temp;
		memset(bucket->_bucket->bucket + (bucket->_bucket->max + 1), false, sizeof(bucket->_bucket->bucket[0]) * (a - bucket->_bucket->max));
		bucket->_bucket->max = a;
	}
	bucket->_bucket->bucket[a] = true;
	return true;
}

static bool Bucket_search(const Bucket *bucket, unsigned k) {
	if (bucket->_bucket->max < k) {
		return false;
	}
	return bucket->_bucket->bucket[k];
}

Bucket* new_Bucket(void) {
	Bucket *bucket = (Bucket*) malloc(sizeof(Bucket));
	if (!bucket)
		return NULL;
	bucket->_bucket = (_Bucket*) malloc(sizeof(_Bucket) + sizeof(bucket->_bucket->bucket[0]));
	if (!(bucket->_bucket)) {
		free(bucket);
		return NULL;
	}
	bucket->_bucket->max = 0;
	bucket->_bucket->bucket[0] = false;
	bucket->insert = Bucket_insert;
	bucket->search = Bucket_search;
	return bucket;
}

void free_Bucket(Bucket **bucket) {
	free((*bucket)->_bucket);
	(*bucket)->_bucket = NULL;
	free(*bucket);
	*bucket = NULL;
}

当然、テストコードも修正しなければなりません。（手戻りの発生した炎上プロジェクトだと思っていただければ）

挿入メソッド
- 配列の最大値を更新する要素
- まだ配列に存在しない要素
- すでに配列に存在する要素
- 今回の入力最大値である1000000のメモリを確保できるか

少なくとも上記のテストをしなければなりません。

BucketTest.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <time.h>
#include <errno.h>
#include "minunit.h"
#include "Bucket.h"

int tests_run = 0;

static char* message_b(size_t k, bool expected, bool actual) {
	static char msg[80];
	sprintf(msg, "[%zu] Error: expected: <%s> but was: <%s>", k,
		expected ? "true" : "false",
		actual ? "true" : "false"
	);
	return msg;
}

static char* message_u(unsigned expected, unsigned actual) {
	static char msg[80];
	sprintf(msg, "Error: expected: <%u> but was: <%u>", expected, actual);
	return msg;
}

static char* test_constructor() {
	Bucket *bucket = new_Bucket();
	mu_assert("Error: expected: <not null> but was: <null>", bucket);
	void* p = (void*) bucket->_bucket;
	unsigned m = *(unsigned*) p;
	bool b = *(bool*) (p + sizeof(unsigned));
	free_Bucket(&bucket);
	mu_assert(message_u(0, m), m == 0);
	mu_assert("Error: expected: <false> but was: <true>", !b);
	mu_assert("Error: expected: <null> but was: <not null>", !bucket);
	return 0;
}

static char* test_insert(size_t n, unsigned *array, bool *expected) {
	bool actual[n];
	Bucket *bucket = new_Bucket();
	for(size_t i = 0; i < n; i++) {
		actual[i] = bucket->insert(bucket, array[i]);
	}
	free_Bucket(&bucket);
	for(size_t i = 0; i < n; i++) {
		mu_assert(message_b(i, expected[i], actual[i]), actual[i] == expected[i]);
	}
	return 0;
}

static char* test_insert_0() {
	bool B[] = {};
	return test_insert(0, NULL, B);
}
static char* test_insert_1() {
	unsigned A[] = {};
	bool B[] = {};
	return test_insert(sizeof(A) / sizeof(A[0]), A, B);
}

static char* test_insert_2() {
	unsigned A[] = {0};
	bool B[] = {true};
	return test_insert(sizeof(A) / sizeof(A[0]), A, B);
}

static char* test_insert_3() {
	unsigned A[] = {0, 0};
	bool B[] = {true, false};
	return test_insert(sizeof(A) / sizeof(A[0]), A, B);
}

static char* test_insert_4() {
	unsigned A[] = {0, 1};
	bool B[] = {true, true};
	return test_insert(sizeof(A) / sizeof(A[0]), A, B);
}

static char* test_insert_5() {
	unsigned A[] = {1, 0};
	bool B[] = {true, true};
	return test_insert(sizeof(A) / sizeof(A[0]), A, B);
}

static char* test_insert_6() {
	unsigned A[] = {1000000};
	bool B[] = {true};
	return test_insert(sizeof(A) / sizeof(A[0]), A, B);
}

static char* test_search_true(unsigned k, size_t n, ...) {
	Bucket *bucket = new_Bucket();
	va_list args;
	va_start(args, n);
	for (size_t i = 0; i < n; i++) {
		bucket->insert(bucket, (unsigned) va_arg(args, unsigned));
	}
	va_end(args);
	bool result = bucket->search(bucket, k);
	free_Bucket(&bucket);
	mu_assert("Error: expected: <true> but was: <false>", result);
	return 0;
}

static char* test_search_false(unsigned k, size_t n, ...) {
	Bucket *bucket = new_Bucket();
	va_list args;
	va_start(args, n);
	for (size_t i = 0; i < n; i++) {
		bucket->insert(bucket, (unsigned) va_arg(args, unsigned));
	}
	va_end(args);
	bool result = bucket->search(bucket, k);
	free_Bucket(&bucket);
	mu_assert("Error: expected: <false> but was: <true>", !result);
	return 0;
}

static char* test_search_0() {return test_search_false(0, 0);}
static char* test_search_1() {return test_search_true(0, 1, 0);}
static char* test_search_2() {return test_search_false(0, 1, 1);}
static char* test_search_3() {return test_search_true(1, 1, 1);}
static char* test_search_4() {return test_search_false(2, 1, 1);}
static char* test_search_5() {return test_search_true(1000000, 1, 1000000);}

static char* all_tests() {
	mu_run_test(test_constructor);
	mu_run_test(test_insert_0);
	mu_run_test(test_insert_1);
	mu_run_test(test_insert_2);
	mu_run_test(test_insert_3);
	mu_run_test(test_insert_4);
	mu_run_test(test_insert_5);
	mu_run_test(test_insert_6);
	mu_run_test(test_search_0);
	mu_run_test(test_search_1);
	mu_run_test(test_search_2);
	mu_run_test(test_search_3);
	mu_run_test(test_search_4);
	mu_run_test(test_search_5);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

エントリポイント

入力チェックとBucketクラスver2を使って、main関数を書き換えます。
※時間計測用のデバッグコードも残しておきます。

main.c

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>
#include "input.h"
#include "Bucket.h"
#ifndef NDEBUG
#include <time.h>
#else
static char* chomp(char *str) {
	if (!str)
		return NULL;
	size_t len = strlen(str);
	while (len--)
		if (isspace(str[len]))
			str[len] = '\0';
		else
			break;
	return str;
}
#endif

int main() {
	size_t N, Q;
#ifdef NDEBUG
	while (true) {
		char s[15];
		if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
			errno = EINVAL;
			for (int c = getchar(); !(c == '\0' || c == '\n' || c == EOF); c = getchar());
		} else if (read_size(chomp(s), &N, &Q)) {
			break;
		}
		perror("The number of elements must be an integer between 1 and 100000.\n"
				"The number of queries must be an integer between 1 and 100000.");
	}
#else
	clock_t start = clock();
	N = 100000;
	Q = 100000;
#endif
	Bucket *bucket = new_Bucket();
	for (size_t i = 0; i < N; i++) {
#ifdef NDEBUG
		while (true) {
			char s[9];
			if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
				errno = EINVAL;
				for (int c = getchar(); !(c == '\0' || c == '\n' || c == EOF); c = getchar());
			} else {
				unsigned a;
				if (read_element(chomp(s), &a)) {
					if (bucket->insert(bucket, a)) {
						break;
					} else if (bucket->_bucket) {
						fprintf(stderr, "The elements of the sequence are duplicated.\n");
						continue;
					} else {
						int e = errno;
						free_Bucket(&bucket);
						perror(NULL);
						return e;
					}
				}
			}
			perror("The element must be an integer between 0 and 1000000.");
		}
#else
		bucket->insert(bucket, (unsigned) (i * 10 + i / 9091));
#endif
	}
	while (Q--) {
		unsigned k;
#ifdef NDEBUG
		while (true) {
			char s[9];
			if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
				errno = EINVAL;
				for (int c = getchar(); !(c == '\0' || c == '\n' || c == EOF); c = getchar());
			} else if (read_element(chomp(s), &k)) {
				break;
			}
			perror("The target must be an integer between 0 and 1000000.");
		}
#else
		k = 900001U + (unsigned) Q;
#endif
		puts(bucket->search(bucket, k) ? "YES" : "NO");
	}
	free_Bucket(&bucket);
#ifndef NDEBUG
	fprintf(stderr, "took %f sec.\n", (float) (clock() - start) / CLOCKS_PER_SEC);
#endif
	return 0;
}

テストコード

最早「単体」テストではないですが、一応テストコードを作るなら、以下のようになります。※特に、system関数使用部は推奨代替案あり。
入力チェックにおいて

字数（バイト数）オーバー
範囲外
配列の重複要素

で再入力が促されることを確認します。

test.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include <errno.h>
#include "minunit.h"
#define SOURCE "main"
#define IN_FILE "in.txt"
#define OUT_FILE "out.txt"
#define ERR_FILE "err.txt"

int tests_run = 0;
char result[100000][5];

static char* message_u(size_t expected, size_t actual) {
	static char msg[80];
	sprintf(msg, "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* message_s(const char *expected, const char *actual) {
	static char msg[80];
	sprintf(msg, "Error: expected: <%s> but was: <%s>", expected, actual);
	return msg;
}

static char* message_ss(size_t k, const char *expected, const char *actual) {
	static char msg[100];
	sprintf(msg, "[%zu] Error: expected: <%s> but was: <%s>", k, expected, actual);
	return msg;
}

static size_t test(size_t n, const char *lines[]) {
	static unsigned k = 0;
	FILE *file;
	if (!(file = fopen(IN_FILE, "w"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	for (size_t i = 0; i < n; i++) {
		fputs(lines[i], file);
		fputc('\n', file);
	}
	fclose(file);
	clock_t start = clock();
	if (!!(errno = system(".\\" SOURCE " <" IN_FILE " 1>" OUT_FILE " 2>" ERR_FILE))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	fprintf(stderr, "#%u %f sec\n", ++k, (float) (clock() - start) / CLOCKS_PER_SEC);
	fflush(stderr);
	if (!(file = fopen(OUT_FILE, "r"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	size_t m = 0;
	while (fgets(result[m], sizeof(result[m]), file)) m++;
	fclose(file);
	return m;
}

static char* test0() {
	const char *lines[] = { "1 1", "0", "0" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(1, n), n == 1);
	mu_assert(message_s("YES\n", result[0]), !strcmp(result[0], "YES\n"));
	return 0;
}

static char* test1() {
	const char *lines[] = { "1 1", "1", "0" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(1, n), n == 1);
	mu_assert(message_s("NO\n", result[0]), !strcmp(result[0], "NO\n"));
	return 0;
}

static char* test2() {
	const char *lines[] = {
		"100000  100000", "0 0", "2 3",
		"10000000", "1000001", "0", "0", "1000000",
		"10000000", "1000001", "0", "1000000", "1"
	};
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(3, n), n == 3);
	mu_assert(message_s("YES\n", result[0]), !strcmp(result[0], "YES\n"));
	mu_assert(message_s("YES\n", result[1]), !strcmp(result[1], "YES\n"));
	mu_assert(message_s("NO\n", result[2]), !strcmp(result[2], "NO\n"));
	return 0;
}

static char* test3() {
	static char *lines[200001] = { "100000 100000" };
	static char chars[200000][8] = {};
	for (size_t i = 0; i < 100000; i++) {
		snprintf(chars[i], sizeof(chars[i]), "%zu", (i + 1) * 10);
		lines[i+1] = chars[i];
	}
	for (size_t i = 100000; i < 200000; i++) {
		snprintf(chars[i], sizeof(chars[i]), "%zu", 800000 + i);
		lines[i+1] = chars[i];
	}
	size_t n = test(sizeof(lines) / sizeof(lines[0]), (const char**) lines);
	mu_assert(message_u(100000, n), n == 100000);
	for (size_t i = 0; i < 100000; i++) {
		if (i % 10) {
			mu_assert(message_ss(i, "NO\n", result[i]), !strcmp(result[i], "NO\n"));
		} else {
			mu_assert(message_ss(i, "YES\n", result[i]), !strcmp(result[i], "YES\n"));
		}
	}
	return 0;
}

static char* all_tests() {
	mu_run_test(test0);
	mu_run_test(test1);
	mu_run_test(test2);
	mu_run_test(test3);
	return 0;
}

int main() {
	if (!!(errno = system("gcc -Wall -Wextra -Werror -DNDEBUG -std=c99 " SOURCE ".c Bucket.c input.c -o " SOURCE " 1>" SOURCE ".txt 2>&1"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		FILE* file = fopen(SOURCE ".txt", "r");
		if (file) {
			int c = 0;
			while ((c = fgetc(file)) != EOF) {
				putchar(c);
			}
			fclose(file);
		}
		return errno;
	}
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	remove(ERR_FILE);
	remove(OUT_FILE);
	remove(IN_FILE);
	remove(SOURCE ".exe");
	remove(SOURCE ".txt");
	if (errno) {
		return errno;
	} else {
		return result != 0;
	}
}

test.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 test.c -o test 1>test.txt 2>&1
if exist test.exe (
	.\test
	echo %ERRORLEVEL%
	del test.exe
	del test.txt
) else (
	type test.txt
)
pause

test3の実行時間は約0.1秒でした。