1.7　查找技术

【考点1】顺序查找（顺序搜索）

（1）基本方法

查找成功：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到。

查找失败：若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素。

（2）以下两种情况只能采用顺序查找：

①线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。

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

（3）顺序查找的缺陷

效率太低。

【考点2】二分法查找（对分查找）

（1）适用范围

只适用于顺序存储的有序表，在此所说的有序表是指线性表中元素按值非递减排列。

（2）具体方法

设有序线性表的长度为n，被查元素为x，则：

①将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；

②若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找

③若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找

④这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。

【真题演练】

在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（　　）。[2013年9月真题]

A．O(n)

B．O(n²)

C．O(log₂n)

D．O(nlog₂n)

【答案】C

【解析】二分查找的最坏情况是不断的二分直至无法再分时，仍然没有查找成功。对于有序的线性表，二分查找法只需比较log₂n次。答案选择C选项。