折半查找 eg:查找key=5的结点所在的数组元素的下标地址 查找不成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector+1]Key;=1,2,n 查找范围:low(低下标)=1;high(高下标)=3; mid=4 key 4 8910111319 45 7 lowE high3( mid-1)
折半查找 0 1 2 mid=4 key e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 查找不成功的情况：数组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 low=1 high=3（mid-1）
折半查找 eg:查找key=5的结点所在的数组元素的下标地址 查找不成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector+1]Key;=1,2,n 查找范围:low(低下标)=1;high(高下标)=3; 比较对象:中点元素,其下标地址为mid=(low+high)/2=2 mid=2 key 4 8910111319 45 7 lowE high3( mid-1)
折半查找 0 1 2 mid=2 key e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 查找不成功的情况：数组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 low=1 high=3（mid-1）
折半查找 eg:查找key=5的结点所在的数组元素的下标地址 查找不成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector+1]Key;=1,2,n 查找范围:low(低下标)=1;high(高下标)=3; 比较对象:中点元素,其下标地址为mid=(low+high)/2=2 mid=2;但key=5<8,向左 key 4 8910111319 45 7 lowE high3( mid-1)
折半查找 0 1 2 mid=2 ; 但 key=5 < 8, 向左 key e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 查找不成功的情况：数组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 low=1 high=3（mid-1）
折半查找 eg:查找key=5的结点所在的数组元素的下标地址 查找不成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector+1]Key;=1,2,n 查找范围:low(低下标)=1;high(高下标)=1 mid=2 key 4 8910111319 7 lowE high=1 (mid-1)
折半查找 0 1 2 mid=2 key e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 查找不成功的情况：数组Vector 如下图所示有序 • 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n • 查找范围：low（低下标）= 1; high（高下标）= 1 4 8 9 10 11 13 19 3 4 5 6 7 low=1 high=1（mid-1）
折半查找 eg:查找key=5的结点所在的数组元素的下标地址 查找不成功的情况:数组 Vector如下图所示有序 数组 Vector:递增序 Vector[.Key<= Vector+1]Key;=1,2,n 查找范围:low(低下标)=1;high(高下标)=1 比较对象:中点元素,其下标地址为mid=(ow+high)/2=1 mid=1 key 4 8910111319 7 lowE high=1
折半查找 0 1 2 mid=1 key e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 查找不成功的情况：数组Vector 如下图所示有序 • 数组 Vector ：递增序 Vector[i]. Key <= Vector[I+1]. Key; i= 1,2,……n • 查找范围：low（低下标）= 1; high（高下标）= 1 •比较对象：中点元素，其下标地址为mid = （low+high）/ 2 = 1 4 8 9 10 11 13 19 3 4 5 6 7 low=1 high=1