第九章查找 925 int Search Sq(ssTable ST, int key )/在有序表上顺序查找的算法,监视哨设在高下 标端 STelem(ST length+1 ].key=key; for(F1; STelem[i]. key>key; i++) if(>ST. lengthIST elem[]. keykey) return ERROR; /ISearch Sq 分析本算法査找成功情况下的平均查找长度为 STrength/2,不成功情况下为 ST length 9.26 int search bin recursive( SSTable ST,int key, int low, int high)折半查找的递归算 i(low>high) retur0,∥查找不到时返回0 mid=-(low+high )/2; if(STelem[mid ]. key==key) return mid else if(STelem(mid ]. key>key) return Search Bin Recursive( st, key, low, mid-1) else return Search Bin Recursive(sT, key, mid+1, high) i //Search Bin Recursive 9.27 Int locate_Bin( SSTable st, int key折半査找,返回小于或等于待查元素的最后 个结点号 int *r STele if(key<r. key )return 0 else if(key>=r[ST length). key) return ST length low=l; high=ST length while (low<=high mid=(low+high)2 if(key>=rmid]key&&key<rmid+1]key)∥查找结束的条件 return mid第九章 查找 9.25 int Search_Sq(SSTable ST,int key)//在有序表上顺序查找的算法,监视哨设在高下 标端 { ST.elem[ST.length+1].key=key; for(i=1;ST.elem[i].key>key;i++); if(i>ST.length||ST.elem[i].key<key) return ERROR; return i; }//Search_Sq 分析:本算法查找成功情况下的平均查找长度为 ST.length/2,不成功情况下为 ST.length. 9.26 int Search_Bin_Recursive(SSTable ST,int key,int low,int high)//折半查找的递归算 法 { if(low>high) return 0; //查找不到时返回 0 mid=(low+high)/2; if(ST.elem[mid].key==key) return mid; else if(ST.elem[mid].key>key) return Search_Bin_Recursive(ST,key,low,mid-1); else return Search_Bin_Recursive(ST,key,mid+1,high); } }//Search_Bin_Recursive 9.27 int Locate_Bin(SSTable ST,int key)//折半查找,返回小于或等于待查元素的最后一 个结点号 { int *r; r=ST.elem; if(key<r .key) return 0; else if(key>=r[ST.length].key) return ST.length; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if(key>=r[mid].key&&key<r[mid+1].key) //查找结束的条件 return mid;