当前位置：首页 > news >正文

顺序查找与折半查找

news 2025/6/4 14:22:50

引言

查找是数据结构和算法中的基础操作之一，其目的是在一组数据中快速定位特定的元素。查找操作广泛应用于数据库查询、搜索引擎、操作系统文件管理等领域。根据数据存储方式的不同，查找方法也有所区别，其中最基础的查找算法包括顺序查找和折半查找（二分查找）。

本实验将围绕这两种基础查找算法进行实现与分析：

顺序查找：适用于无序的数据集合，通过逐一比较来查找目标值；
折半查找：要求数据有序，利用“中间点”缩小查找范围，效率更高。

我们将通过实际编程演示两种查找算法的具体实现过程，理解其原理、适用场景及实现注意事项。

一、顺序查找的实现

1.1 实验需求分析

我们需要实现一个顺序查找程序，该程序应具备以下功能：

创建并初始化一个查找表；
向查找表中填充给定的数据；
使用顺序查找算法查找指定关键字；
输出查找结果（成功或失败）；
程序运行过程中输出必要的调试信息，便于观察查找流程。

输入数据为：{5, 17, 21, 23, 31, 41, 49, 62, 68, 89}，待查关键字为 41。

1.2 代码思路构建

顺序查找是一种最简单的查找方式，其核心思想是从头到尾逐个比较数组中的元素，直到找到目标值或者遍历完整个数组为止。

实现思路如下：

定义一个查找表结构体，用于保存数据数组及其长度；
编写初始化函数，将初始数据填入结构体；
编写顺序查找函数，接收查找表和目标关键字，返回目标索引；
编写打印函数，根据查找结果输出相应信息；
在主函数中调用上述函数完成整个查找流程。

1.3 代码实现

1.3.1 查找表结构体定义

首先，我们需要定义一个查找表结构体，用于存储查找的数据以及总数据大小。

/*** 查找表结构体定义*/
typedef struct 
{int data[MAX_TABLE_SIZE];     // 存储数据的数组int size;                     // 当前表长度
} SearchTable;

补充：数据数组中的宏定义表示当前数组可存储的最大容量，自己编写时需要注意加上

1.3.2 初始化查找表

初始化函数，即负责将预设的数组数据复制到查找表结构体中，并记录当前表的长度。同时输出每个元素的值和索引位置，方便查看初始化情况。

void InitSearchTable(SearchTable* table)
{int dataSize = sizeof(initialData) / sizeof(initialData[0]);// 数据复制到查找表for (int i = 0; i < dataSize; ++i){table->data[i] = initialData[i];printf("元素 %d: 值 = %d, 索引 = %d\n", i + 1, table->data[i], i);}table->size = dataSize;  // 设置当前表长度printf("查找表已初始化，共 %d 个元素。\n", table->size);
}

【注意事项】

需要确保传入的 table 指针不为空；
使用 sizeof 计算数组长度时要注意数组不能退化为指针；
初始化完成后必须设置 size 成员变量。
其中可能有未见定义的变量，这实际上是全局变量，并非漏定义，后续也是同理；

1.3.3 顺序查找函数

顺序查找函数从数组第一个元素开始，依次比较每个元素是否等于目标关键字。若找到则立即返回索引；否则继续查找直至结束。

【代码如下】

int SeqSearch(const SearchTable* table, const int key)
{// 参数合法性校验if (table == NULL || table->size <= 0){printf("错误：查找表为空或无效。\n");return FAIL;}// 遍历查找表进行查找for (int i = 0; i < table->size; ++i){if (table->data[i] == key){return i;  // 找到，返回索引}}return FAIL;  // 未找到
}

【注意事项】

必须检查查找表是否为空或无效；
查找过程中一旦找到目标就立刻返回，避免多余计算；
若未找到，返回定义的 FAIL 标志（-1）。

1.3.4 结果输出函数

结果输出函数根据查找函数的返回值判断是否找到目标值，并输出相应的提示信息。

【代码如下】

void PrintResult(int index, const int key)
{if (index != FAIL){printf("查找成功：关键字 %d 在查找表中的位置为索引 %d。\n", key, index);}else{printf("查找失败：关键字 %d 未在查找表中找到。\n", key);}
}

【注意事项】

注意区分 index 是否为 -1 来判断查找结果；
输出语句应清晰明了，便于用户理解查找状态。

1.4 主函数测试

// 给定查找表内容及待查关键字
const int initialData[] = { 5, 17, 21, 23, 31, 41, 49, 62, 68, 89 };
const int key = 41;/*** 主函数：执行顺序查找操作*/
int main(void)
{/* 创建查找表对象 */SearchTable searchTable;                       printf("\n\t=== 顺序查找演示 ===\n\n");/* 初始化查找表 */InitSearchTable(&searchTable);  /* 执行顺序查找 */int resultIndex = SeqSearch(&searchTable, key);/* 输出查找结果 */PrintResult(resultIndex, key);return 0;
}

二、折半查找的实现

2.1 实验需求分析

我们需要实现一个折半查找程序，要求如下：

创建并初始化一个查找表；
填充原始数据后对其进行排序；
使用折半查找算法查找指定关键字；
输出查找结果；
运行过程中输出排序后的数组内容，以验证排序正确性。

输入数据为：{5, 54, 16, 48, 72, 45, 24, 86, 33, 19}，待查关键字为 24。

2.2 代码思路构建

折半查找是一种高效的查找方式，但前提是数据必须是有序的。其实现逻辑如下：

将原始数据排序（升序）；
设定查找区间起始 low 和结束 high；
取中间位置 mid，比较中间值与目标值：
- 相等则返回 mid；
- 中间值小于目标，则在右半区间查找；
- 中间值大于目标，则在左半区间查找；
重复上述步骤，直到找到或区间无效为止。

实现步骤：

定义查找表结构体；
编写初始化函数并排序；
编写折半查找函数；
编写打印函数；
主函数中调用所有函数完成查找流程。

2.3 代码实现

2.3.1 查找表结构体定义（复用）

同理，和顺序表定义查找表结构体相同，可直接复用。

/*** 查找表结构体定义*/
typedef struct 
{int data[MAX_TABLE_SIZE];     // 存储数据的数组int size;                     // 当前表长度
} SearchTable;

补充：数据数组中的宏定义表示当前数组可存储的最大容量，自己编写时需要注意加上

2.3.2 初始化查找表并排序

初始化函数将原始数据复制到查找表中，然后使用标准库函数 qsort 对数据进行升序排序。排序后输出各元素的位置信息。

【代码如下】

void InitSearchTable(SearchTable* table)
{int dataSize = sizeof(initialData) / sizeof(initialData[0]);// 数据复制到查找表for (int i = 0; i < dataSize; ++i){table->data[i] = initialData[i];}// 对查找表进行升序排序qsort(table->data, dataSize, sizeof(int), CompareInts);table->size = dataSize;  // 设置当前表长度// 输出排序后的各元素位置信息printf("排序后的线性表各元素位置信息：\n");for (int i = 0; i < table->size; ++i){printf("索引 %d: 值 = %d\n", i, table->data[i]);}printf("\n查找表已初始化并排序，共 %d 个元素。\n", table->size);
}

【注意事项】

排序前需确保数据有效；
qsort 函数需要自定义比较函数；
排序完成后必须更新 size 字段。

2.3.2 快速排序比较函数

为了配合 qsort 使用，我们需要一个比较函数，用于决定排序顺序。此处实现的是升序排列。

int CompareInts(const void* a, const void* b)
{// 升序 反转即降序return (*(int*)a - *(int*)b);
}

【注意事项】

参数类型为 const void*，需强制转换为 int*；
返回值决定了排序顺序，负数表示 a 应在前面，正数表示 b 应在前面；
此函数仅适用于整型数组排序。

2.3.3 折半查找函数

折半查找函数维护两个边界 low 和 high，每次取中间位置 mid，比较中间值与目标值，从而缩小查找范围。

【代码如下】

int BinarySearch(const SearchTable* table, int key)
{// 参数合法性校验if (table == NULL || table->size <= 0){printf("错误：查找表为空或无效。\n");return FAIL;}int low = 0;int high = table->size - 1;while (low <= high){int mid = (low + high) / 2;  // 中间索引计算if (table->data[mid] == key){return mid;  // 找到，返回索引}else if (table->data[mid] < key){low = mid + 1;  // 在右半部分查找}else{high = mid - 1;  // 在左半部分查找}}return FAIL;  // 未找到
}

【注意事项】

必须保证查找表已排序；
mid 的计算应防止溢出，但在此例中数据量小无需特殊处理；
查找失败时返回 FAIL。

2.3.4 结果输出函数（复用）

由于顺序查找和折半查找的结果格式相同，因此可以直接复用 PrintResult 函数。

【代码如下】

void PrintResult(int index, int key)
{if (index != FAIL){printf("查找成功：关键字 %d 在查找表中的位置为索引 %d。\n", key, index);}else{printf("查找失败：关键字 %d 未在查找表中找到。\n", key);}
}

【注意事项】

无需修改，可直接复用；
要确保 index 的含义一致（即 -1 表示未找到）。

2.4 主函数测试

// 给定查找表内容及待查关键字
const int initialData[] = { 5, 54, 16, 48, 72, 45, 24, 86, 33, 19 };
const int key = 24;/*** 主函数：执行折半查找操作*/
int main(void)
{/* 创建查找表对象 */SearchTable searchTable;printf("\n\t=== 折半查找演示 ===\n");/* 初始化查找表（包含排序） */InitSearchTable(&searchTable);/* 执行折半查找 */int resultIndex = BinarySearch(&searchTable, key);/* 输出查找结果 */PrintResult(resultIndex, key);return 0;
}