二分查找
又稱為折半查找（Binary Search）
它要求線性表中結點必須按關鍵字值遞增或遞減順序排列
二分查找的基本思想
首先用要查找的關鍵字K與中間位置的結點的關鍵字相比較
這個中間結點把線性表分成了兩個子表
若比較結果相等則查找完成
若不相等
再根據K與該中間結點關鍵字的比較大小確定下一步查找哪個子表
這樣遞歸下去
直到找到滿足條件的結點或者該線性表中沒有這樣的結點
二分查找示例
在等概率假設下
二分查找成功時的平均查找長度近似於lg(n+
)
在查找失敗時所需比較的關鍵字個數不超過判定樹的深度
在最壞情況下查找成功的比較次數也不超過判定樹的深度┌lg(n+
)┐
二分查找只適用於順序存儲結構
From:http://tw.wingwit.com/Article/program/sjjg/201311/23621.html
