鄂尔多斯网站推广,抚顺网站建设服务电话,做网站工商局要不要备案呢,淄博做网站市场目录
1、顺序查找
定义及步骤
代码实现
2、折半查找
定义及步骤
代码实现
折半查找判定树
3、分块查找
定义及步骤 1、顺序查找
定义及步骤 顺序查找的定义#xff1a;从数据集合的起始位置开始#xff0c;逐一比较每个数据元素#xff0c;直到找到所要查找…目录
1、顺序查找
定义及步骤
代码实现
2、折半查找
定义及步骤
代码实现
折半查找判定树
3、分块查找
定义及步骤 1、顺序查找
定义及步骤 顺序查找的定义从数据集合的起始位置开始逐一比较每个数据元素直到找到所要查找的元素或者遍历完整个数据集合为止。适用于顺序表链表表中元素有无顺序都可以。其时间复杂度为O(n)其中n为待查找元素个数。
具体步骤如下 从集合的第一个元素开始顺序遍历直到找到目标元素或者遍历完整个集合。 若遍历到的元素与目标元素相同则返回该元素的位置。 若遍历完整个集合仍未找到目标元素则返回未找到的标识通常为-1。 代码实现
下面是 C 语言实现顺序查找带哨兵的示例代码
#include stdio.h#define MAXSIZE 100 // 定义最大容量typedef struct {int data[MAXSIZE1]; // 数据存储数组从 data[1] 开始存储数据int len; // 当前长度
} SeqList;// 初始化顺序表
void initList(SeqList *list) {for (int i 1; i MAXSIZE; i) {list-data[i] 0;}list-len 0;
}// 插入元素
int insertList(SeqList *list, int elem) {if (list-len MAXSIZE) { // 判断是否已满return 0;}list-data[list-len] elem;return 1;
}// 带哨兵的顺序查找
int searchList(SeqList *list, int elem) {int i;list-data[0] elem; // 设置哨兵for (i list-len; list-data[i] ! elem; i--); // 从后向前遍历查找return i; // 返回查找到的位置
}int main() {SeqList list;initList(list);insertList(list, 1);insertList(list, 3);insertList(list, 5);insertList(list, 7);insertList(list, 9);int pos searchList(list, 5);if (pos 0) {printf(未找到\n);} else {printf(找到了位置为%d\n, pos);}return 0;
}在上面的代码中我们定义了一个 SeqList 结构体来实现顺序表其中包含了数据存储数组和当前长度。使用 initList 函数进行初始化使用 insertList 函数插入数据。在 searchList 函数中我们设置了一个哨兵然后从后向前遍历查找如果找到则返回位置否则返回 0 表示未找到。在主函数中我们创建了一个顺序表插入了一些数据然后进行查找输出查找结果。 2、折半查找
定义及步骤 折半查找Binary Search又称为二分查找是一种基于比较目标值和数组中间元素的查找算法。该算法的前提条件是数组必须已经有序。只适用于顺序表仅适用于顺序存储结构不适用于链式存储结构。
具体实现过程为
1. 定义左右指针分别指向数组的第一个元素和最后一个元素。
2. 然后取中间元素的下标将目标值与此元素进行比较。如果目标值等于数组中间元素的值则直接返回中间元素的下标。
3. 如果目标值小于数组中间元素的值则将右指针移动到中间元素的左边一位。
4. 如果目标值大于数组中间元素的值则将左指针移动到中间元素的右边一位。
5. 重复步骤2~4直到目标值与中间元素相等或者左右指针相遇。
6. 如果左右指针相遇时仍没有找到目标值则表示该数组中没有目标值。
折半查找算法的时间复杂度是O(logN)相对于顺序查找的时间复杂度O(N)而言折半查找具有更高的效率。 代码实现
下面是 C 语言实现折半查找的示例代码
#include stdio.hint binarySearch(int array[], int left, int right, int x) {while (left right) {int mid left (right - left) / 2;if (array[mid] x) {return mid;}else if (array[mid] x) {left mid 1;}else {right mid - 1;}}return -1; //表示未找到
}int main() {int array[] {1, 3, 5, 7, 9, 11};int x 5;int n sizeof(array) / sizeof(array[0]);int result binarySearch(array, 0, n - 1, x);if (result -1) {printf(未找到该元素\n);}else {printf(元素在数组中的索引是%d\n, result);}return 0;
}上述代码中binarySearch函数的参数依次是数组array、数组左边界left、数组右边界right和要查找的元素x。函数通过while循环不断缩小查找范围最终返回要查找元素在数组中的索引。在主函数中我们定义了一个有序数组然后调用binarySearch函数查找元素5在数组中的位置。如果返回-1则表示未找到该元素否则返回元素在数组中的索引。 注意该算法要求在查找之前需要先对数组进行排序。因此如果数组没有排序需要先调用排序算法进行排序再进行查找。
折半查找判定树 折半查找判定树Binary Search Decision TreeBSDT是一种二叉树用于解决折半查找Binary Search问题。在BSDT中每个节点代表一个比较操作左节点表示小于比较值右节点表示大于比较值。叶节点代表查找成功的结果非叶节点代表查找失败的结果。
例如对于一个长度为7的有序数组[1, 2, 3, 4, 5, 6, 7]对应的BSDT如下图所示 ______4______/ \___2___ __6__/ \ / \1 3 5 7在BSDT中从根节点4开始如果要查找数字3则先和根节点比较由于3小于4因此向左子节点2移动。然后再和2节点比较由于3大于2因此向右子节点3移动。最终到达叶节点查找成功。 对于长度为n的有序数组BSDT的高度为log₂(n)因为每次比较可以剔除一半的数据因此最多需要比较log₂(n)次。由于BSDT的高度与数据的顺序无关因此对于任何有序数组BSDT都可以处理。 虽然BSDT的时间复杂度是O(log₂(n))与折半查找一样但是BSDT比折半查找更适合用于动态数据集合因为BSDT可以实时更新支持插入、删除等操作。
3、分块查找 定义及步骤 分块查找是一种查找算法它是一种特殊的二分查找用于在一组有序的数据中查找特定元素。分块查找主要用于在数据量大时可以减少比较次数快速查找所需的元素。
分块查找的过程分为以下几个步骤 将数据分成若干个块将查找的数据分割为若干块块的大小可自行决定。每一块内的元素是有序的块与块之间的元素大小可以不同。 对每一块内的元素建立索引对每一块内的元素建立索引索引可以是一个指向元素位置的指针或是一个存储最大元素值的数组。 使用二分查找在索引中查找所在块根据查找的元素值在索引中使用二分查找找到相应的块。 在所在块中进行线性查找在所在块中使用线性查找查找所需元素直到找到与之相等的元素或者超出所在块的范围为止。 返回查找结果如果找到所需的元素则返回该元素的位置如果未找到则返回不存在的信息。 需要注意的是分块查找的块大小和索引的大小对算法的效率有很大影响。一般来说块的大小不要太大索引的大小不要太小这样才能充分利用分块查找的优势减少查找次数提高查找效率。
