五种查找算法总结.docx

《五种查找算法总结.docx》由会员分享，可在线阅读，更多相关《五种查找算法总结.docx（2页珍藏版）》请在第一文库网上搜索。

1、五种查找算法总结一、挨次查找条件：无序或有序队列。原理：按挨次比较每个元素，直到找到关键字为止。时间简单度：0(n)二、二分查找(折半查找)条件：有序数组原理：查找过程从数组的中间元素开头，假如中间元素正好是要查找的元素，则搜素过程结束；假如某特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开头一样从中间元素开头比较。假如在某一步骤数组为空，则代表找不到。这种搜寻算法每一次比较都使搜寻范围缩小一半。时间简单度：O(logn)三、二叉排序树查找条件：先创建二又排序树：1 .若它的左子树不空，则左子树上全部结点的值均小于它的根结点的值；2 .若它的右子树不空，则右子树

2、上全部结点的值均大于它的根结点的值；3 .它的左、右子树也分别为二又排序树。原理：在二叉查找树b中查找x的过程为：1 .若b是空树，则搜寻失败，否则：2 .若x等于b的根节点的数据域之值，则查找胜利；否则：3 .若x小于b的根节点的数据域之值，则搜寻左子树；否则：4 .查找右子树。时间简单度： O(log2(n)四、哈希表法（散列表）条件：先创建哈希表（散列表）原理：依据键值方式（Key value）进行查找，通过散列函数，定位数据元素。时间简单度：几乎是0（1）,取决于产生冲突的多少。五、分块查找原理：将n个数据元素”按块有序“划分为m块（m n）0每一块中的结点不必有序，但块与块之间必需”按块有序。即第1块中任一元素的关键字都必需小于第2块中任一元素的关键字：而第2块中任一元素又都必需小于第3块中的任一元素，。然后使用二分查找及挨次查找。