《考点7 查找技术》由会员分享,可在线阅读,更多相关《考点7 查找技术(7页珍藏版)》请在金锄头文库上搜索。
考点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)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。,疑难解答:二分查找法适用于哪种情况? 二分查找法只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大,但允许相邻元素值相等)。,