2011年计算机二级公共基础知识考点知识7

　　1.7.1顺序查找 (P33)

　　顺序查找又称顺序搜索。

　　对于大的线性表来说，顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：

　　(1) 线性表无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。

　　(2) 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。

　　1.7.2二分法查找 (P33—P34)

　　二分法查找只适用于顺序存储的有序表。

　　显然，当有序线性表为顺序存储时都能采用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。