當前位置:成語大全網 - 新華字典 - 二分法比較次數

二分法比較次數

二分法檢索要求線性表結點按關鍵碼值排序且以順序方式存儲。在查找時,首先與表的中間位置上結點的關鍵值比較,若相等則檢索成功;否則根據比較結果確定下壹步在表的前半部或後半部中繼續進行。二分法檢索的效率較高,設線性表有n個元素,則最多的檢索次數為大於log2 n 的最小整數,最少的檢索次數為1。

二分法檢索又稱折半檢索,二分法檢索的基本思想是設字典中的元素從小到大有序地存放在數組中,首先將給定值key與字典中間位置上元素的關鍵碼比較,如果相等,則檢索成功;否則,若key小,則在字典前半部分中繼續進行二分法檢索,若key大,則在字典後半部分中繼續進行二分法檢索。這樣,經過壹次比較就縮小壹半的檢索區間,如此進行下去,直到檢索成功或檢索失敗。二分法檢索是壹種效率較高的檢索方法,要求字典在順序表中按關鍵碼排序