Algorithms and Datastructures: Search 1、静态查找表 2、有序表的查找 折半查找(或二分查找法) 1、应用范围:顺序表,表内元素之间有序。不可直接用于线性链表。 eg:查找key=9的结点所在的数组元素的下标地址。 查找成功的情况:数组 STele如下图所示有序 数组 STele:递增序 STelen[Key<= STele+们Key;i1,2, 查找范围:ow(低下标)=1;high(高下标)=3; mid=4 key 8910111319 011 23↑4567 high=3( mid-1) 16 SEAR
16 物料管理 SEAR 16 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=4 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 ; 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、应用范围:顺序表,表内元素之间有序。不可直接用于线性链表。 eg:查找key=9的结点所在的数组元素的下标地址。 查找成功的情况:数组 STele如下图所示有序 数组 STele:递增序 STelen[Key<= STele+们Key;i1,2, 查找范围:ow(低下标)=1;high(高下标)=3; 比较对象:中点元素,其下标地址为md=(ow+hgh)/2」=2 mid=2 key 8910111319 011 23↑4567 high=3( mid-1) SEAR
17 物料管理 SEAR 17 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=2 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 =2 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、应用范围:顺序表,表内元素之间有序。不可直接用于线性链表。 eg:查找key=9的结点所在的数组元素的下标地址。 查找成功的情况:数组 STele如下图所示有序 数组 STele:递增序 STelen[Key<= STele+们Key;i1,2, 查找范围:ow(低下标)=1;high(高下标)=3; 比较对象:中点元素,其下标地址为md=(ow+hgh)/2」=2 mid=2;但key=9>8,向右 key 8910111319 011 23↑4567 high=3( mid-1) 18 SEAR
18 物料管理 SEAR 18 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=2; 但 key=9 > 8, 向右 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 =2 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、应用范围:顺序表,表内元素之间有序。不可直接用于线性链表。 eg:查找key=9的结点所在的数组元素的下标地址。 查找成功的情况:数组 STele如下图所示有序 数组 STele:递增序 STelen[Key<= STele+们Key;i1,2, 查找范围:ow(低下标)=3;high(高下标)=3; mid=2 key 489 10111319 01213↑4567 high=3 low=3(mid+1) SEAR
19 物料管理 SEAR 19 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 key e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组ST.elem 如下图所示有序 • 数组 ST.elem ：递增序ST.elem[i]. Key <= ST.elem[I+1]. Key; i= 1,2,……n-1 • 查找范围：low（低下标）= 3; high（高下标）= 3 ; 4 8 9 10 11 13 19 3 4 5 6 7 high=3 low=3（mid+1） mid=2
Algorithms and Datastructures: Search 1、静态查找表 2、有序表的查找 折半查找(或二分查找法) 1、应用范围:顺序表,表内元素之间有序。不可直接用于线性链表。 eg:查找key=9的结点所在的数组元素的下标地址。 查找成功的情况:数组 STele如下图所示有序 数组 STele:递增序 STelen[Key<= STele+们Key;i1,2, 查找范围:ow(低下标)=3;high(高下标)=3; 比较对象:中点元素,其下标地址为md=(ow+hgh)/2]=3 mid=3: key 8910111319 01213↑4567 high=3 low=3 SEAR
20 物料管理 SEAR 20 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=3; key e.g: 查找 key = 9 的结点所在的数组元素的下标地址。 查找成功的情况：数组ST.elem 如下图所示有序 • 数组 ST.elem ：递增序ST.elem[i]. Key <= ST.elem[I+1]. Key; i= 1,2,……n-1 • 查找范围：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