二分法檢索要求線性表結點按關鍵碼值排序且以順序方式存儲.在查找時,首先與表的中間位置上結點的關鍵值比較,若相等則檢索成功;否則根據比較結果確定下一步在表的前半部或后半部中繼續(xù)進行.二分法檢索的效率較高,設線性表有n個元素,則最多的檢索次數為大于log2 n 的最小整數,最少的檢索次數為1.
二分法檢索又稱折半檢索,二分法檢索的基本思想是設字典中的元素從小到大有序地存放在數組中,首先將給定值key與字典中間位置上元素的關鍵碼比較,如果相等,則檢索成功；否則,若key小,則在字典前半部分中繼續(xù)進行二分法檢索,若key大,則在字典后半部分中繼續(xù)進行二分法檢索.這樣,經過一次比較就縮小一半的檢索區(qū)間,如此進行下去,直到檢索成功或檢索失敗.二分法檢索是一種效率較高的檢索方法,要求字典在順序表中按關鍵碼排序