|
|
|
|
|
顺序查找的基本思想是：从表的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。
|
|
|
|
|
|
一般情况下，ci=n-i+1，因此在等概率情况下，顺序查找成功的平均查找长度为
|
|
|
|
|
|
也就是说，成功查找的平均次数约为表长的一半。与其他方法相比，顺序查找方法在n值较大时，其平均查找长度较大，查找效率较低。但这种方法也有优点，就是算法简单且适应面广，对查找表的结构没有要求，无论记录是否按关键字有序排列均可使用。
|
|
|
|
|
|
折半查找的基本思想是：设查找表的元素存储在一维数组r[1…n]中，那么在表中的元素已经按关键字递增（或递减）的方式排序的情况下，可进行折半查找。其方法是：首先将待查的key值与表r中间位置上（下标为mid）记录的关键字进行比较，若相等则查找成功；若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1…n]中，下一步应在后半个子表中再进行折半查找；若key<r[mid].key，说明待查记录只可能在前半个子表r[1…mid-1]中，下一步应在r的前半个子表中进行折半查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。
|
|
|
折半查找的性能分析：折半查找的过程可以用一棵二叉树描述，不妨设节点总数为n=2h-1，则判定树是深度为h=log2(n+1)的满二叉树。在等概率情况下，折半查找的平均查找长度为 。
|
|
|
|
当n值较大时，ASLbs≈log2(n+1)-1。
|
|
|
|
折半查找比顺序查找的效率高，但它要求查找表进行顺序存储并且按关键字有序排列，因此对表进行元素的插入和删除时，需要移动大量的元素，所以折半查找适用于表不易变动，且又经常进行查找的情况。
|
|
|
|
|
|
分块查找又称为索引顺序查找，是对顺序查找方法的一种改进，其性能介于顺序查找和二分查找之间。
|
|
|
|
分块查找的基本思想是：在分块查找过程中，首先把表分成若干块，每一块中的关键字不一定有序，但块之间是有序的，即后一块中所有记录的关键字均大于前一个块中最大的关键字。此外，还建立了一个索引表，索引表按关键字有序。所以分块查找的过程分为两步：第一步在索引表中确定待查记录所在的块；第二步在块内顺序查找。
|
|
|
