1.7 查找技术
: j( {. e: k7 `7 s 查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。8 s' H6 a9 Q/ L w1 `" l
查找结果:(查找成功:找到;查找不成功:没找到。)
4 y; S1 i6 i y* T, _2 @" }3 M 平均查找长度:查找过程中关键字和给定值比较的平均次数。2 u- P+ J9 P: R. }
1、顺序查找( f( i* Q3 s' o& O/ J
基本思想:从表中的第一个元素开始,将给定的值与表中逐个元素的关键字进行比较,直到两者相符,查到所要找的元素为止。否则就是表中没有要找的元素,查找不成功。* w8 B6 F7 g0 D* ~
在平均情况下,利用顺序查找法在线性表中查找一个元素,大约要与线性表中一半的元素进行比较,最坏情况下需要比较n次。
' U* u7 u) M: E3 T0 e 顺序查找一个具有n个元素的线性表,其平均复杂度为O(n)。
. }, h6 O, N( Z# E8 Y: Q 下列两种情况下只能采用顺序查找:% f K6 j3 w6 w+ T. Z- L6 I
1)如果线性表是无序表(即表中的元素是无序的),则不管是顺序存储结构还是链式存储结构,都只能用顺序查找。
3 z2 E9 b% V( ]; N7 ~- r 2)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。
3 A7 S/ @( N2 K! I 2、二分法查找
9 o: ]* S) ]( s4 t/ B 思想:先确定待查找记录所在的范围,然后逐步缩小范围,直到找到或确认找不到该记录为止。
. r% [: x0 K9 _& e3 h5 @ 前提:必须在具有顺序存储结构的有序表中进行。$ {" ^1 r, Q4 g5 W; f$ B
查找过程:( P( K% n) ?1 I4 v7 e3 E9 S" T
1)若中间项(中间项mid=(n-1)/2,mid的值四舍五入取整)的值等于x,则说明已查到;
$ e; ^( }; M/ B( s5 s- K 2)若x小于中间项的值,则在线性表的前半部分查找;5 `) _1 a& s: z( Z( F" S# \ ^( ^4 q1 u
3)若x大于中间项的值,则在线性表的后半部分查找。
0 w, V; W0 R! i& m 特点:比顺序查找方法效率高。最坏的情况下,需要比较log2n次。# l" l3 }3 V) T0 q( w
*:二分法查找只适用于顺序存储的线性表,且表中元素必须按关键字有序(升序)排列(注释1)。对于无序线性表和线性表的链式存储结构只能用顺序查找。在长度为n的有序线性表中进行二分法查找,其时间复杂度为O(log2n)。 |