查找

从前到后- 线性查找 -就是顺序查找.

哨兵法查找–节省每次都要判断是否越界的这一步骤利于节省开销，从而提升效率。

参考我的程序

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