Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 ·折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.g:查找key=9的结点所在的数组元素的下标地址。 查找成功的情况：数组sT.elem如下图所示有序 ·数组sT.elem:递增序ST.elem[).Key<=ST.elem[I-+1].Key;i=1,2,.n-1 ·查找范围：low(低下标)=1；high(高下标)=3； ·比较对象：中点元素，其下标地址为mid=(low+high)I2=3 mid=3;但key=9中点值也为9，找到 key 4 8 9 10 11 13 19 2 3 4 5 6 high=3 21 low=3 SEAR
21 物料管理 SEAR 21 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=3; 但 key=9 中点值也为9 ，找到 key e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组ST.elem 如下图所示有序 • 数组 ST.elem ：递增序ST.elem[i]. Key <= ST.elem[I+1]. Key; i= 1,2,.n-1 • 查找范围：low（低下标）= 1; high（高下标）= 3 ; • 比较对象：中点元素，其下标地址为mid = （low+high）/ 2 = 3 4 8 9 10 11 13 19 3 4 5 6 7 high=3 low=3
Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 ·折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.g:查找key=5的结点所在的数组元素的下标地址。 查找不成功的情况：数组sT.elem如下图所示有序 ·数组sT.elem:递增序ST.elem[).Key<=ST.elem[l+1].Key;i=1,2,.n-1 ·查找范围：low(低下标)=1；high(高下标)=7（初始时为最大下标n); ·比较对象：中点元素，其下标地址为mid=(Iow+high)I2J mid=4但key=5<10,向左 key 4 8 9 10 11 13 19 0 2 3 4 5 6 low=1 high=7 22 SEAR
22 物料管理 SEAR 22 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=4 但 key=5 < 10, 向左 key e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 查找不成功的情况：数组ST.elem 如下图所示有序 • 数组 ST.elem ：递增序ST.elem[i]. Key <= ST.elem[I+1]. Key; i= 1,2,.n-1 • 查找范围：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
Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 ·折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.g:查找key=5的结点所在的数组元素的下标地址。 查找不成功的情况：数组sT.elem如下图所示有序 ·数组sT.elem:递增序ST.elem).Key<=ST.elem[l+1].Key;=1,2.n-1 ·查找范围：Iow(低下标)=1；high(高下标)=3； mid=4 key 4 8 9 10 11 13 19 2 3 4 5 6 7 low=1 high=3 (mid-1) 23 SEAR
23 物料管理 SEAR 23 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=4 key e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 查找不成功的情况：数组ST.elem 如下图所示有序 • 数组 ST.elem ：递增序ST.elem[i]. Key <= ST.elem[I+1]. Key; i= 1,2,.n-1 • 查找范围：low（低下标）= 1; high（高下标）= 3 ; 4 8 9 10 11 13 19 3 4 5 6 7 low=1 high=3（mid-1）
Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 ·折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.g:查找key=5的结点所在的数组元素的下标地址。 查找不成功的情况：数组sT.elem如下图所示有序 ·数组sT.elem:递增序ST.elem[).Key<=ST.elem[l+1].Key;i=1,2,.n-1 ·查找范围：low(低下标)=1；high(高下标)=3； ·比较对象：中点元素，其下标地址为mid=(Iow+high)I2J=2 mid=2 key 4 8 9 10 11 13 19 0 1 2 3 4 5 6 7 low=1 high=3 24 SEAR
24 物料管理 SEAR 24 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=2 key e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 查找不成功的情况：数组ST.elem 如下图所示有序 • 数组 ST.elem ：递增序ST.elem[i]. Key <= ST.elem[I+1]. Key; i= 1,2,.n-1 • 查找范围：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
Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 ·折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.g:查找key=5的结点所在的数组元素的下标地址。 查找成功的情况：数组sT.elem如下图所示有序 ·数组sT.elem:递增序ST.elem)].Key<=ST.elem+1].Key;i片1,2，n-1 ·查找范围：low(低下标)=1；high(高下标)=3； ·比较对象：中点元素，其下标地址为mid=(1ow+high)I2=2 mid=2;但key=5<8,向左 key 4 8 9 10 11 13 19 0 2 3 4 5 6 low=1 high=3 25 SEAR
25 物料管理 SEAR 25 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=2; 但 key=5 < 8, 向左 key e.g: 查找 key = 5 的结点所在的数组元素的下标地址。 查找成功的情况：数组ST.elem 如下图所示有序 • 数组 ST.elem ：递增序ST.elem[i]. Key <= ST.elem[I+1]. Key; i= 1,2,.n-1 • 查找范围：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