西西軟件園多重安全檢測(cè)下載網(wǎng)站、值得信賴(lài)的軟件下載站!
軟件
軟件
文章
搜索

首頁(yè)編程開(kāi)發(fā)其它知識(shí) → 程序員必須知道的8大排序和3大查找

程序員必須知道的8大排序和3大查找

相關(guān)軟件相關(guān)文章發(fā)表評(píng)論 來(lái)源:shan9liang時(shí)間:2012/5/11 9:51:01字體大。A-A+

作者:shan9liang點(diǎn)擊:8913次評(píng)論:0次標(biāo)簽: 程序員

Java程序員appv2.3.0 官網(wǎng)安卓版
  • 類(lèi)型:教育學(xué)習(xí)大。8.6M語(yǔ)言:中文 評(píng)分:10.0
  • 標(biāo)簽:
立即下載
12 頁(yè) 二分法查找(折半查找)

二、二分法查找(折半查找)的基本思想:


前提:

(1)確定該區(qū)間的中點(diǎn)位置:mid=(low+high)/2    

min代表區(qū)間中間的結(jié)點(diǎn)的位置,low代表區(qū)間最左結(jié)點(diǎn)位置,high代表區(qū)間最右結(jié)點(diǎn)位置

(2)將待查a值與結(jié)點(diǎn)mid的關(guān)鍵字(下面用R[mid].key)比較,若相等,則查找成功,否則確定新的查找區(qū)間:

如果R[mid].key>a,則由表的有序性可知,R[mid].key右側(cè)的值都大于a,所以等于a的關(guān)鍵字如果存在,必然在R[mid].key左邊的表中。這時(shí)high=mid-1

如果R[mid].key<a,則等于a的關(guān)鍵字如果存在,必然在R[mid].key右邊的表中。這時(shí)low=mid

如果R[mid].key=a,則查找成功。

(3)下一次查找針對(duì)新的查找區(qū)間,重復(fù)步驟(1)和(2)

(4)在查找過(guò)程中,low逐步增加,high逐步減少,如果high<low,則查找失敗。



平均查找長(zhǎng)度=Log2(n+1)-1

注:雖然二分法查找的效率高,但是要將表按關(guān)鍵字排序。而排序本身是一種很費(fèi)時(shí)的運(yùn)算,所以二分法比較適用于順序存儲(chǔ)結(jié)構(gòu)。為保持表的有序性,在順序結(jié)構(gòu)中插入和刪除都必須移動(dòng)大量的結(jié)點(diǎn)。因此,二分查找特別適用于那種一經(jīng)建立就很少改動(dòng)而又經(jīng)常需要查找的線性表。

    相關(guān)評(píng)論

    閱讀本文后您有什么感想? 已有人給出評(píng)價(jià)!

    • 8 喜歡喜歡
    • 3 頂
    • 1 難過(guò)難過(guò)
    • 5 囧
    • 3 圍觀圍觀
    • 2 無(wú)聊無(wú)聊

    熱門(mén)評(píng)論

    最新評(píng)論

    發(fā)表評(píng)論 查看所有評(píng)論(0)

    昵稱(chēng):
    表情: 高興 可 汗 我不要 害羞 好 下下下 送花 屎 親親
    字?jǐn)?shù): 0/500 (您的評(píng)論需要經(jīng)過(guò)審核才能顯示)