折半查找 应用范围:顺序表,表内元素之间有序。不可直接用于线性链表 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=9>8,向右 key 4 8910111319 23 45 7 lowE high=3(mid-1)
折半查找 应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=2;但 key=9 > 8, 向右 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
折半查找 应用范围:顺序表,表内元素之间有序。不可直接用于线性链表 eg:查找key=9的结点所在的数组元素的下标地址 查找成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector[+1.Key;i1,2,…n 查找范围:low(低下标)=3;high(高下标)=3 mid=2 key 4 8910111319 213145 7 low=3 high=3(mid-1) d+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（低下标）= 3; high（高下标）= 3 4 8 9 10 11 13 19 3 4 5 6 7 high=3 (mid -1) low=3 (mid +1)
折半查找 应用范围:顺序表,表内元素之间有序。不可直接用于线性链表 eg:查找key=9的结点所在的数组元素的下标地址 查找成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector+1]Key;=1,2,n 查找范围:low(低下标)=3;high(高下标)=3 比较对象:中点元素,其下标地址为mid=l(low+hjgh)12」=3 id=3 key 4 8 93 10111319 4 7 low=3 h
折半查找 应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=3 key e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组Vector 如下图所示有序 • 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n • 查找范围：low（低下标）= 3; high（高下标）= 3 • 比较对象：中点元素，其下标地址为mid = （low+high）/ 2 =3 4 8 9 10 11 13 19 3 4 5 6 7 high=3 low=3
折半查找 应用范围:顺序表,表内元素之间有序。不可直接用于线性链表 eg:查找key=9的结点所在的数组元素的下标地址 查找成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector+1]Key;=1,2,n 查找范围:ow(低下标)=3;high(高下标)=3 比较对象:中点元素,其下标地址为mid=(low+high)/2=3 mid=3;key=9且中点值也为9,找到 key 4 8 93 10111319 4 7 low=3 h
折半查找 应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=3; key=9 且中点值也为9 ，找到 key e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组Vector 如下图所示有序 • 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n •查找范围：low（低下标）= 3; high（高下标）= 3 • 比较对象：中点元素，其下标地址为mid = （low+high）/ 2 =3 4 8 9 10 11 13 19 3 4 5 6 7 high=3 low=3
折半查找 eg:查找key=5的结点所在的数组元素的下标地址 查找不成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector+1]Key;=1,2,n ·查找范围:ow(低下标)=1;high(高下标)=7(初始时为最大下标n); 比较对象:中点元素,其下标地址为mid=(low+high)/2」 mid=4但key=5<10,向左 key 4 8910111319 lowE high=7
折半查找 0 1 2 mid=4 但 key=5 < 10, 向左 key e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 查找不成功的情况：数组Vector 如下图所示有序 • 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n • 查找范围：low（低下标）= 1; high（高下标）= 7 （初始时为最大下标n ）; • 比较对象：中点元素，其下标地址为mid = （low+high）/ 2 4 8 9 10 11 13 19 3 4 5 6 7 high=7 low=1