C语言算法之查找

一.查找相关概念

这一部分解释数据结构里面查找的相关基础概念：

• 查找：在数据集合中寻找满足某种条件的数据元素的过程。
• 查找表：用于查找的数据集合
• 关键字：数据元素中唯一标识该元素的某个数据项的值
• 静态查找表：静态查找表是指在查找表建立后，查找表中的元素不再发生变化。
• 动态查找表：动态查找表是指在查找表建立后，查找表中的元素可能会发生增加、删除等变化。
• 查找长度：查找长度是指在进行一次查找操作时，需要比较的关键字的个数
• 平均查找长度：平均查找长度是指进行n次查找操作时，所有查找长度之和除以n的结果。

二.顺序查找（线性查找）

1.对象

• 静态查找表
• 线性表（顺序表、链表）

2.原理

从数据结构的起始位置开始，依次检查每个元素，直到找到目标元素或到达数据结构的末尾为止。

具体步骤如下：

1. 从数据结构的第一个元素开始遍历，依次和目标元素进行比较。
2. 如果当前元素等于目标元素，则返回该元素位置。
3. 如果已经遍历完所有元素（即到达数据结构的末尾）仍未找到目标元素，则返回查找失败。

顺序查找的时间复杂度为O(n)，其中n为数据结构中元素的数量。当数据量较小或者数据结构没有特定的有序性质时，顺序查找是一个常用的查找方法。

3.代码

typedef struct{                        //查找表的数据结构(顺序表)
ElemType *elem;                        //动态数组基址
int TableLen;                           //表的长度
}SSTable;//顺序查找
int Search_ _Seq(SSTable ST, ElemType key){int i;for( i=0;i<ST. TableLen)&& ST.elem[i] !=key; ++i);        //查找成功，则返回元素下标;查找失败，则返回-1return i==ST.TableLen? (-1): i;
}

三.折半查找（二分查找）

1.对象

• 静态查找表
• 有序的顺序表

2.原理

它的原理基于以下思想：

1. 首先确定待查找区间的左右端点 mid、left 和 right，并计算出中间位置 mid。
2. 将要查找的值与 mid 位置上的元素进行比较。如果相等，则返回 mid；否则，判断查找值与 mid 元素大小的关系，若小于 mid 位置的元素，则在左侧区间继续查找；否则，在右侧区间继续查找。
3. 不断重复以上操作，直到找到目标元素或者区间为空。

具体地，折半查找的实现步骤如下：

1. 初始化 left 和 right 为数组的左右端点，即 left=0，right=n-1，其中 n 表示数组的长度。
2. 计算 mid 位置，即 mid = (left + right) / 2。
3. 判断查找值是否等于 mid 位置上的元素，如果是，则返回 mid。如果不是，则比较查找值和 mid 位置上的元素大小关系，如果小于 mid 位置上的元素，则从 left 到 mid - 1 的区间内继续查找；否则，从 mid + 1 到 right 的区间内继续查找。
4. 重复步骤 2 和 3，直到找到目标元素或者区间为空。

需要注意的是，折半查找只适用于有序数组。如果数组没有排序，则需要先对数组进行排序。

折半查找（二分查找）的时间复杂度是 O(log n)。

3.代码

typedef struct{                        //查找表的数据结构(顺序表)
ElemType *elem;                        //动态数组基址
int TableLen;                           //表的长度
}SSTable;//折半查找
int Binary_ Search(SSTable L, ElemType key){int Low=0, high=L.TableLen-1,mid;while(low<=high){mid=(low+high)/2;           //取中间位置if(L.elem [mid]==key)return mid;             //查找成功则返回所在位置else if(L.elem[mid]>key)high=mid-1;             //从前半部分继续查找elselow=mid+1;              //从后半部分继续查找}return - 1;                     //查找失败，返回-1 
}

四.分块查找（索引顺序查找）

1.思想

它的基本思想是将有序表分成若干个块，每个块中存储多个关键字，并且块之间按照关键字的大小顺序连接起来。这样就形成了一个“块链”。

在进行查找时，先在块中进行二分查找，如果找到了关键字，则返回；若未找到，则需要在相邻的块中继续查找。由于块之间是有序的，因此可以采用类似于二分查找的方法来确定需要进入哪个块中进行查找，从而可以减少查找的次数，提高查找效率。

分块查找的时间复杂度为 O(√n)，其中 n 表示有序表中元素的个数。虽然它的效率不如二分查找，但是在某些特定情况下，如查找次数较少、表比较大等情况下，分块查找仍然具有一定的优势。

2.C语言模拟分块查找

int blockSearch(int arr[], int n, int x, int blockSize) {// 计算块数int blocks = (int)ceil((double)n / blockSize);// 数组 index 表示每个块的起始下标，maxIndex 表示当前块中最大的下标int index[blocks], maxIndex[blocks];for (int i = 0; i < blocks; i++) {index[i] = i * blockSize;maxIndex[i] = (i + 1) * blockSize - 1;if (maxIndex[i] >= n) {maxIndex[i] = n - 1;}}// 查找所在块int block = -1;for (int i = 0; i < blocks; i++) {if (arr[index[i]] <= x && arr[maxIndex[i]] >= x) {block = i;break;}}// 块内顺序查找if (block == -1) {return -1;}for (int i = index[block]; i <= maxIndex[block]; i++) {if (arr[i] == x) {return i;}}return -1;
}

五.哈希函数

1.哈希函数

哈希函数是将任意大小的数据映射到固定大小的数据的一种函数。在哈希表中，哈希函数通常用于将关键字映射到桶的索引上，以便于快速定位元素。

哈希函数的设计非常重要，它直接影响了哈希表的性能。一个好的哈希函数应该满足以下几个条件：

1. 映射均匀：哈希函数应该尽量让不同的关键字映射到不同的桶中，从而避免冲突的发生。一个映射均匀的哈希函数可以使得每个桶中元素的数量尽可能均衡，也可以减少线性探测或者拉链法时的查找次数。
2. 易于计算：哈希函数的计算速度应该尽可能快，这样可以提高哈希表的建立和查询效率。
3. 低冲突率：哈希函数应该尽量避免冲突的发生，即不同的关键字映射到相同的桶中，因为冲突会导致查找效率下降。如果无法完全避免冲突，那么就需要选择一种合适的冲突处理方式，如开放寻址法、线性探测、拉链法等。

哈希函数的设计方法有很多种，常见的包括直接取模法、乘法取整法、平方取中法等。具体如何选择和设计哈希函数需要根据具体问题和数据特征进行考虑。

2.举例

以下是一个简单的哈希函数，使用了取模法将关键字映射到桶中：

int hash(int key, int buckets) {return key % buckets;
}

这个哈希函数接受两个参数：key 表示要映射的关键字，buckets 表示哈希表的大小（即桶的数量）。该函数将关键字 key 对哈希表的大小进行取模运算，得到的余数就是关键字在哈希表中对应的桶的索引。

需要注意的是，该哈希函数不一定适用于所有情况，因为它可能会导致冲突的发生。例如，如果哈希表的大小与某些关键字的倍数有关，那么这些关键字就会被映射到同一个桶中，从而影响查找效率。为了避免这种情况，我们需要选择更加复杂的哈希函数，并根据实际情况进行调整和优化。

六.说明

新星计划：数据结构与算法，@西安第一深情，创作打卡2！