具有12個(gè)關(guān)鍵字的有序表，折半查找的平均長度是多少？半搜索的平均長度是3.1。二元搜索的決策樹為：6/3 9//1 47 11/2 58 10 12平均搜索長度=1/12*（1*1 2*2 3*4 4

具有12個(gè)關(guān)鍵字的有序表，折半查找的平均長度是多少？

半搜索的平均長度是3.1。二元搜索的決策樹為：6/3 9//1 47 11/2 58 10 12平均搜索長度=1/12*（1*1 2*2 3*4 4*5）=37/12。=3.1.擴(kuò)展數(shù)據(jù)：半搜索法更有效。假設(shè)有五個(gè)整數(shù)A0~A4從小到大排列，要搜索的數(shù)字是X，基本思想是：讓搜索數(shù)據(jù)范圍的下限為l=0，上限為h=4，找到中點(diǎn)M=（lh）/2，將X與中點(diǎn)元素am進(jìn)行比較，如果X等于am，則找到并停止搜索。該方法將搜索范圍縮小了一半，提高了搜索效率。