Question

数据结构与算法顺序查找和折半查找

Answer 1

1.顺序查找
又称线性查找，主要用于在线性表中进行查找。

一般线性表的顺序查找：
从线性表的一端开始，逐个检查关键字满足给定条件。若查找到某个元素的关键字满足给定条件则查找成功，返回该元素在线性表中的位置。若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。

有序表的顺序查找：
假设表L是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为key。当查找到第i个元素时，发现第i个元素对应的关键字小于key，但第i+1个元素对应的关键字大于key，这时就可以返回查找失败的信息。

2.折半查找
又称二分查找，它仅适用于有序的顺序表

首先将给定值key与表中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置。若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止。或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

3.分块查找
又称按索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找

将查找表分为若干子块。块内的元素可以无序，但块之间是有序的，第一个块中的最大关键字小于第二个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列