查找

從前到后- 線性查找 -就是順序查找.

哨兵法查找–節省每次都要判斷是否越界的這一步驟利于節省開銷，從而提升效率。

參考我的程序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>#define SIZE 100000000// 普通遍歷查找
bool normal_search(int arr[], int key, int size) {for (int i = 0; i < size; i++) {if (arr[i] == key) {return true;}}return false;
}// 哨兵優化查找
int sentinel_search(int arr[], int key, int size) {int last = arr[size - 1];arr[size - 1] = key; // 設置哨兵int i = 0;while (arr[i] != key) {i++;}arr[size - 1] = last; // 恢復原數據if (i < size - 1 || key == last) {return i;} else {return -1;}
}int main() {int *arr = (int *)malloc(SIZE * sizeof(int));if (arr == NULL) {fprintf(stderr, "內存分配失敗\n");return 1;}// 初始化數組為升序排列for (int i = 0; i < SIZE; i++) {arr[i] = i;}clock_t start, end;double normal_time, sentinel_time;// 測試普通查找start = clock();normal_search(arr, SIZE - 1, SIZE);end = clock();normal_time = (double)(end - start) / CLOCKS_PER_SEC;// 測試哨兵查找start = clock();sentinel_search(arr, SIZE - 1, SIZE);end = clock();sentinel_time = (double)(end - start) / CLOCKS_PER_SEC;printf("數組大小: %d\n", SIZE);printf("普通查找耗時: %f 秒\n", normal_time);printf("哨兵查找耗時: %f 秒\n", sentinel_time);printf("性能提升: %.2f%%\n", (normal_time - sentinel_time) / normal_time * 100);free(arr);return 0;
}

二叉排序樹

更便于查找的數據結構，他的查找效率，要比順序表高太多了。
極大利于數據操作中的【查找】

左孩子節點 < 父節點B < 右孩子節點

查找嘎嘎快。

普通

#include <stdio.h>
#include <stdlib.h>#define SIZE 10000000// 普通順序查找
bool normal_search(int arr[], int size, int val) {for (int i = 0; i < size; i++) {if (arr[i] == val) return true;}return false;
}int main() {int *arr = (int*)malloc(SIZE * sizeof(int));if (arr == NULL) {fprintf(stderr, "內存分配失敗\n");return 1;}// 初始化數組為升序排列for (int i = 0; i < SIZE; i++) {arr[i] = i;}int target = SIZE - 1; // 查找目標值bool found = normal_search(arr, SIZE, target);printf("數據量= %d  \n",SIZE);printf("普通查找結果: %s\n", found ? "找到" : "未找到");free(arr);return 0;
}

bst

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define SIZE 1000000// 二叉排序樹節點結構
typedef struct Node {int data;struct Node *left;struct Node *right;
} Node;// 插入節點（迭代實現）
Node* insert(Node* root, int val) {Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = val;newNode->left = newNode->right = NULL;if (root == NULL) return newNode;Node *curr = root;while (1) {if (val < curr->data) {if (curr->left == NULL) {curr->left = newNode;break;} else {curr = curr->left;}} else {if (curr->right == NULL) {curr->right = newNode;break;} else {curr = curr->right;}}}return root;
}// BST查找（迭代實現）
bool bst_search(Node* root, int val) {while (root != NULL) {if (root->data == val) return true;else if (val < root->data) root = root->left;else root = root->right;}return false;
}// 釋放BST內存
void free_bst(Node* root) {if (root == NULL) return;free_bst(root->left);free_bst(root->right);free(root);
}int main() {srand(time(NULL));Node *root = NULL;// 初始化BST（隨機數據）for (int i = 0; i < SIZE; i++) {root = insert(root, rand() % (SIZE * 10));}int target = SIZE - 2; // 查找目標值bool found = bst_search(root, target);printf("BST數據量= %d  \n",SIZE);printf("BST查找結果: %s\n", found ? "找到" : "未找到");free_bst(root);return 0;
}