熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構之二分查找

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23621.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.