例如:key=64的查找过程如下 STlength STele 0513192137566475808892 01234567891011 low high mid=(low+high)/2 Low指示查找区间的下界 hih指示查找区间的上界 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elem ST.length 例如: key=64 的查找过程如下 low high mid low mid high mid mid = (low+high)/2 Low 指示查找区间的下界 high 指示查找区间的上界
012345678 6103468102 搜索ow mid 6 high 5678 6810121 6116 low mid high 搜索成功的例子 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 搜索成功的例子 6 -1 0 1 3 4 6 8 10 12 0 1 2 3 4 5 6 7 8 搜索 low mid 6 high 6 8 10 12 5 6 7 8 low mid high 6 6 5 low mid high 6
012345678 51013|46|81102 搜索ow mid 5 high 5678 6181012 low mid 5 56 low mid high 搜索失败的例子 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 搜索失败的例子 5 -1 0 1 3 4 6 8 10 12 0 1 2 3 4 5 6 7 8 搜索 low mid 5 high 6 8 10 12 5 6 7 8 low mid high 5 6 5 low mid high 5
int Search Bin(TB ST, TYPE key f low =1; high=STlength; while(low<=high) i mid=(lowthigh)/2; if(key=-ST. mid. keyreturn mid if(key<sTelem(mid]. key high=mid-1; if(key>STelemmid key )low=mid+1; return 0; 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 int Search_Bin(TB ST, TYPE key) { low = 1; high = ST.length; while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid].key)return mid; if(key<ST.elem[mid].key)high=mid-1; if(key>ST.elem[mid].key)low=mid+1; } return 0; }
有序顺序表的折半搜索的判定树 (10,2030,40,50,60) 0 50 20 40 60) 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 有序顺序表的折半搜索的判定树 ( 10, 20, 30, 40, 50, 60 ) 10 50 = = = = = = 30 < < < < < < > > > > > > 20 40 60