二分探索法の基本ロジック
要素が昇順に整列された配列に対し、目的のキーが含まれるインデックスを対数時間で特定する関数です。境界値の更新順序と終了条件の設計が正しさの鍵となります。
参考実行枠組み
#include <stdio.h>
#include <stdlib.h>
#define MAX_CAPACITY 10
#define SEARCH_FAILED 0
typedef int ValueT;
typedef int IndexT;
typedef struct SeqList *Sequence;
struct SeqList {
ValueT elements[MAX_CAPACITY];
IndexT size; /* 有効な最後の添字 */
};
Sequence CreateSequence(); /* 外部提供：下位1開始で初期化 */
IndexT PerformBinarySearch( Sequence S, ValueT target );
int main() {
Sequence list;
ValueT query;
IndexT result;
list = CreateSequence();
scanf("%d", &query);
result = PerformBinarySearch(list, query);
printf("%d\n", result);
return 0;
}
/* ここに検索関数の本体を実装してください */実行サンプル
入力例1：
5
12 31 55 89 101
31出力例1：
2入力例2：
3
26 78 233
31出力例2：
0実装例
IndexT PerformBinarySearch( Sequence S, ValueT target )
{
if (!S) return SEARCH_FAILED;
int left_bound = 1;
int right_bound = S->size;
int pivot_idx;
while (left_bound <= right_bound) {
pivot_idx = (left_bound + right_bound) / 2;
if (S->elements[pivot_idx] < target) {
left_bound = pivot_idx + 1;
} else if (S->elements[pivot_idx] > target) {
right_bound = pivot_idx - 1;
} else {
return pivot_idx;
}
}
return SEARCH_FAILED;
}線形探査によるハッシュテーブル検索
衝突が発生した際、次の空いているバケットへ順次移動してデータを取得するアプローチです。テーブルが一杯の場合のエラーハンドリングが必要です。
ハッシュテーブル構造定義
#include <stdio.h>
#define TABLE_MAX_CAP 100000
typedef int KeyT;
typedef int PosT;
typedef enum { ENTRY_ACTIVE, SLOT_FREE, REMOVED_FLAG } CellState;
typedef struct Slot BucketCell;
struct Slot {
KeyT value;
CellState status;
};
typedef struct HashTable *HashTbl;
struct HashTable {
int capacity;
BucketCell *slots;
};
HashTbl InitializeTable();
PosT CalculateHash( KeyT key, int cap ) {
return (key % cap);
}
#define FIND_ERR -1
PosT LocateKey( HashTbl tbl, KeyT key );
int main() {
HashTbl table;
KeyT search_key;
PosT found_pos;
table = InitializeTable();
scanf("%d", &search_key);
found_pos = LocateKey(table, search_key);
if (found_pos == FIND_ERR)
printf("ERROR: %d is not found and the table is full.\n", search_key);
else if (table->slots[found_pos].status == ENTRY_ACTIVE)
printf("%d is at position %d.\n", search_key, found_pos);
else
printf("%d is not found. Position %d is returned.\n", search_key, found_pos);
return 0;
}
/* 検索関数をここに記述 */実行サンプル
11
11 88 21 -1 -1 5 16 7 6 38 10
3838 is at position 9.41 is not found. Position 3 is returned.実装例
PosT LocateKey( HashTbl tbl, KeyT key )
{
PosT current_scan, origin_hash;
int probe_count = 0;
origin_hash = CalculateHash(key, tbl->capacity);
current_scan = origin_hash;
while (tbl->slots[current_scan].value != key && tbl->slots[current_scan].status != SLOT_FREE) {
probe_count++;
if (probe_count >= TABLE_MAX_CAP)
return FIND_ERR;
current_scan = (origin_hash + probe_count) % tbl->capacity;
}
return current_scan;
}チェイン法におけるエントリ削除
各バケットが連結リストを保持する方式です。指定文字列に一致するノードを見つけ、メモリを開放してポインタチェーンを更新する処理を実装します。
主要構造体とインターフェース
#include <stdio.h>
#include <string.h>
#define STR_LEN 15
typedef char StringT[STR_LEN + 1];
typedef int HashIdx;
typedef enum { FALSE, TRUE } Bool;
typedef struct ListNode *LinkNode;
struct ListNode {
StringT payload;
LinkNode next_ref;
};
typedef LinkNode NodePtr;
typedef struct ChainHash *ChainTbl;
struct ChainHash {
int bucket_count;
NodePtr heads;
};
HashIdx ComputeHash( StringT str, int count ) {
return (str[0] - 'a') % count;
}
ChainTbl SetupTable();
Bool ExecuteDelete( ChainTbl tbl, StringT str_to_remove );
int main() {
ChainTbl hash_map;
StringT input_str;
hash_map = SetupTable();
scanf("%s", input_str);
if (ExecuteDelete(hash_map, input_str) == FALSE)
printf("ERROR: %s is not found\n", input_str);
else
printf("Are you kidding me?\n");
return 0;
}
/* 削除関数の実装 */実行サンプル
ableable is deleted from list Heads[0]dateERROR: date is not found実装例
Bool ExecuteDelete( ChainTbl tbl, StringT target )
{
NodePtr prev_link, curr_link;
HashIdx head_index;
head_index = ComputeHash(target, tbl->bucket_count);
prev_link = &(tbl->heads[head_index]);
curr_link = tbl->heads[head_index].next_ref;
while (curr_link && strcmp(curr_link->payload, target)) {
prev_link = curr_link;
curr_link = curr_link->next_ref;
}
if (!curr_link) return FALSE;
printf("%s is deleted from list Heads[%d]", target, head_index);
prev_link->next_ref = curr_link->next_ref;
free(curr_link);
return TRUE;
}二つの整列済み配列の中央値算出
両方の配列を結合せずに、交互に要素を取り出すことで中央値を算出するスライディング窓アルゴリズムの実装例です。
入力形式
5
1 3 5 7 9
2 3 4 5 6出力：4
6
-100 -10 1 1 1 1
-50 0 2 3 4 5出力：1
実装例
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int arr_first[100001], arr_second[100001];
int combined[200002];
for (int i = 0; i < n; i++) scanf("%d", &arr_first[i]);
for (int i = 0; i < n; i++) scanf("%d", &arr_second[i]);
int ptr_a = 0, ptr_b = 0;
int merge_idx = 0;
while (ptr_a < n && ptr_b < n) {
if (arr_first[ptr_a] < arr_second[ptr_b]) {
combined[merge_idx++] = arr_first[ptr_a++];
} else {
combined[merge_idx++] = arr_second[ptr_b++];
}
}
while (ptr_a < n) combined[merge_idx++] = arr_first[ptr_a++];
while (ptr_b < n) combined[merge_idx++] = arr_second[ptr_b++];
int mid_index = (merge_idx - 1) / 2;
printf("%d", combined[mid_index]);
return 0;
}同一の二分探索木判定
異なる順序で挿入されたノード群が、内部構造および要素値において完全に一致するかを検証する再帰アルゴリズムです。
入力サンプル
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0出力：
Yes
No
No実装例
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode *left_child;
TreeNode *right_child;
TreeNode(int v) : data(v), left_child(nullptr), right_child(nullptr) {}
};
void InsertIntoTree(TreeNode*& root, int val) {
if (!root) {
root = new TreeNode(val);
return;
}
if (val < root->data)
InsertIntoTree(root->left_child, val);
else
InsertIntoTree(root->right_child, val);
}
bool TreesAreIdentical(TreeNode* t1, TreeNode* t2) {
if (!t1 && !t2) return true;
if (t1 && t2) {
if (t1->data == t2->data)
return TreesAreIdentical(t1->left_child, t2->left_child) &&
TreesAreIdentical(t1->right_child, t2->right_child);
}
return false;
}
int main() {
int n, l;
while (cin >> n && n != 0) {
cin >> l;
TreeNode *ref_tree = nullptr;
int val;
for (int i = 0; i < n; i++) {
cin >> val;
InsertIntoTree(ref_tree, val);
}
TreeNode *test_tree = nullptr;
for (int k = 0; k < l; k++) {
test_tree = nullptr;
for (int i = 0; i < n; i++) {
cin >> val;
InsertIntoTree(test_tree, val);
}
cout << (TreesAreIdentical(ref_tree, test_tree) ? "Yes" : "No") << endl;
}
}
return 0;
}完全二分探索木の検証
配列をヒープ形式のインデックス割り当てで表現し、末尾に未割り当ての空缺がないかをチェックする完全性判定ロジックです。
入力サンプル
9
38 45 42 24 58 30 67 12 51出力：
38 45 24 58 42 30 12 67 51
YES8
38 24 12 45 58 67 42 51出力：
38 45 24 58 42 12 67 51
NO実装例
#include <cstdio>
#include <cstring>
int heap_arr[105];
int total_nodes;
void PlaceValue(int idx, int val) {
if (heap_arr[idx] == 0) {
heap_arr[idx] = val;
return;
}
if (val > heap_arr[idx])
PlaceValue(idx * 2, val);
else
PlaceValue(idx * 2 + 1, val);
}
int main() {
int inserted_val;
scanf("%d", &total_nodes);
memset(heap_arr, 0, sizeof(heap_arr));
for (int i = 0; i < total_nodes; i++) {
scanf("%d", &inserted_val);
PlaceValue(1, inserted_val);
}
int print_count = 0;
int scan_idx = 1;
bool is_complete = true;
for (int i = 1; i <= total_nodes * 2 + 1; i++) {
if (heap_arr[i] != 0) {
if (print_count) printf(" ");
printf("%d", heap_arr[i]);
print_count++;
} else if (print_count < total_nodes) {
is_complete = false;
}
}
printf("\n%s\n", is_complete ? "YES" : "NO");
return 0;
}