考点7 查找技术,2012.01.16,顺序查找,依次找 Best 第一个 Worst n次 Avenue n/2 次 时间复杂度：O（n),二分查找,条件：顺序存储结构线性表有序表（小大 允许相邻=）,二分法查找元素x过程：,1、x 比较 线性表中间项 log2n2、 x=中间项 successx中间项 前半部分 （F）x中间项 后半部分 （F）,结束： Success / 子表长度=0,例子,数据结构中，能用二分法查找的是顺序存储的有序线性表,在下列两种情况下也只能采用顺序查找： （1）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。 （2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,疑难解答：二分查找法适用于哪种情况？ 二分查找法只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。,