顺序查找的性能 设n为结点的总数。 平均查找长度AVL( Average Search Length) 成功查找情况下:设每个结点的査找概率相等 ASL=>((n-1+1)n) En (n+1)/2
顺序查找的性能 • 设 n 为结点的总数。 平均查找长度AVL（Average Search Length ） 成功查找情况下：设每个结点的查找概率相等 1 ASL＝∑(( n-i+1) ) i=n ＝ （n+1）/ 2 1 n
顺序查找的性能 一般查找情况下(包括成功、不成功两种情况):设成功与不成功两种情况 可能性相等,每个结点的查找概率也相等。 AsL=x(n+1)2n)+x(n+1)20 =3(n+1)4 013810100 10010081 3 3456共有n+1=7种不成功的查找情况
顺序查找的性能 一般查找情况下（包括成功、不成功两种情况）：设成功与不成功两种情况 可能性相等，每个结点的查找概率也相等。 1 ASL＝∑(( n-i+1) ) +∑((n+1) ) ＝ 3(n+1)/4 0 1 2 100 10 0 8 1 3 3 4 5 6 0 1 3 10 8 100 共有n+1=7种不成功的查找情况 2n 1 2(n+1) 1 1 i=n i=n+1
折半查找(二分查找) 应用范围:顺序表,表内元素之间有序。不可直接用于线性链表 eg:查找key=9的结点所在的数组元素的下标地址 查找成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector[+1.Key;i1,2,…n 查找范围:ow(低下标)=1;high(高下标)=7(初始时为最大下标n); 比较对象:中点元素,其下标地址为mid=(low+high)/2=4 mid=4但key=9<10,向左 key 4 8910111319 lowE high=7
折半查找（二分查找） 应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=4 但 key=9 < 10, 向左 key e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组Vector 如下图所示有序 • 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n •查找范围：low（低下标）= 1; high（高下标）= 7 （初始时为最大下标 n ）; • 比较对象：中点元素，其下标地址为mid = （low+high）/ 2 =4 4 8 9 10 11 13 19 3 4 5 6 7 high=7 low=1
折半查找 应用范围:顺序表,表内元素之间有序。不可直接用于线性链表 eg:查找key=9的结点所在的数组元素的下标地址 查找成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector[+1.Key;i1,2,…n 查找范围:low(低下标)=1;high(高下标)=3 mid=4 key 4 8910111319 23 45 7 lowE high=3(mid-1)
折半查找 应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=4 key e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组Vector 如下图所示有序 • 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n • 查找范围：low（低下标）= 1; high（高下标）= 3 4 8 9 10 11 13 19 3 4 5 6 7 high=3 (mid -1) low=1
折半查找 应用范围:顺序表,表内元素之间有序。不可直接用于线性链表 eg:查找key=9的结点所在的数组元素的下标地址 查找成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector+1]Key;=1,2,n 查找范围:low(低下标)=1;high(高下标)=3 比较对象:中点元素,其下标地址为mid=l(low+hjgh)12」=2 mid=2 key 4 8910111319 23 45 7 lowE high=3(mid-1)
折半查找 应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=2 key e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组Vector 如下图所示有序 • 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n • 查找范围：low（低下标）= 1; high（高下标）= 3 • 比较对象：中点元素，其下标地址为mid = （low+high）/ 2 =2 4 8 9 10 11 13 19 3 4 5 6 7 high=3 (mid -1) low=1