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(高下标)=1； mid=2 key 4 8 9 10 11 13 19 0 2 3 4 5 6 7 low=1 26 high=1 (mid-1) SEAR
26 物料管理 SEAR 26 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（高下标）= 1 ; 4 8 9 10 11 13 19 3 4 5 6 7 high=1（mid-1） low=1
Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 ·折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 e.g:查找key=5的结点所在的数组元素的下标地址。 查找成功的情况：数组sT.elem如下图所示有序 ·数组sT.elem:递增序ST.elem[).Key<=ST.elem[I-+1].Key;i=1,2,.n-1 ·查找范围：low(低下标)=1；high(高下标)=1； ·比较对象：中点元素，其下标地址为mid=(low+high)I2=1 mid=1 key 4 8 9 10 11 13 19 0 2 3 4 5 6 low=1 27 high=1 SEAR
27 物料管理 SEAR 27 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=1 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（高下标）= 1 ; • 比较对象：中点元素，其下标地址为mid = （low+high）/ 2 = 1 4 8 9 10 11 13 19 3 4 5 6 7 high=1 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;i=1,2,.n-1 ·查找范围：low(低下标)=1；high(高下标)=1； ·比较对象：中点元素，其下标地址为mid=(low+high)I2=1 mid=1;但key=5>4,向右 key 8 9 10 11 13 19 0 2 3 5 6 7 low=1 28 high=1 SEAR
28 物料管理 SEAR 28 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 • 折半查找（或二分查找法） 1、应用范围：顺序表，表内元素之间有序。不可直接用于线性链表。 0 1 2 mid=1; 但 key=5 > 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（高下标）= 1 ; • 比较对象：中点元素，其下标地址为mid = （low+high）/ 2 = 1 4 8 9 10 11 13 19 3 4 5 6 7 high=1 low=1
Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 ·折半查找（或二分查找法） 1、顺序表，表内元素之间有序。不可直接用于线性链表。 e.g:查找key=5的结点所在的数组元素的下标地址。 查找成功的情况：数组sT.elem如下图所示有序 ·数组sT.elem:递增序ST.elem).Key<=ST.elem+1].Key;ie1,2,.n-1 ·查找范围：low(低下标)=1；high(高下标)=1； ·比较对象：中点元素，其下标地址为mid=(Iow+high)I2=1 失败条件：low>high;处于间 mid=1;但key=5>4,向右 隙中的键值导致这种情况！ key 4 8 9 10 11 13 19 2 3 4 5 6 7 1ow=2 (mid+1) 29 high=1 SEAR
29 物料管理 SEAR 29 Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 0 1 2 mid=1; 但 key=5 > 4, 向右 key 4 8 9 10 11 13 19 3 4 5 6 7 high=1 low=2 （mid+1） 失败条件：low > high; 处于间 隙中的键值导致这种情况！ • 折半查找（或二分查找法） 1、顺序表，表内元素之间有序。不可直接用于线性链表。 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（高下标）= 1 ; • 比较对象：中点元素，其下标地址为mid = （low+high）/ 2 = 1
Algorithms and DataStructures:Search 1、静态查找表 2、有序表的查找 ·折半查找（或二分查找法） 2、程序实现 表示：typedef struct{ElemType*elem;int length;}SStable;∥length=n int Search_bin(SStable ST,KeyType key) ∥在有序表中查找关键字之值为ky的结点，找到返回该结点 ∥在表中的下标地址，否则返回0 low =1;high=ST.length while(low <high) mid =low +ligh)/2 if (EQ(ST.elem[mid].key,key)return mid; else if(LT(key,ST.elem[mid].key )high=mid-1; else low mid +1; } return 0: }∥Search_Bin 30 SEAR
30 物料管理 SEAR 30 Algorithms and DataStructures:Search 1、静态查找表 表示：typedef struct { ElemType * elem; int length; } SStable; // length = n int Search_bin ( SStable ST, KeyType key ) // 在有序表中查找关键字之值为key 的结点，找到返回该结点 // 在表中的下标地址，否则返回0 { low = 1 ; high = ST.length ; while ( low <= high ) { mid = ( low + ligh ) / 2 ; if ( EQ(ST.elem[mid]. key, key ) return mid ; else if ( LT( key , ST.elem[mid]. key ) ) high = mid -1 ; else low = mid + 1; } return 0 ； } // Search_Bin 2、有序表的查找 • 折半查找（或二分查找法） 2、程序实现