二分查找算法速記

chinafgj 發(fā)布于2019-07-01 12:43 / 3244人閱讀

摘要：二分查找英語，也稱折半搜索英語對(duì)數(shù)搜索英語，是一種在有序數(shù)組中查找某一特定元素的搜索算法。這種搜索算法每一次比較都使搜索范圍縮小一半。代碼實(shí)現(xiàn)參考文章算法通關(guān)講

二分查找（英語：binary search），也稱折半搜索（英語：half-interval search）對(duì)數(shù)搜索（英語：logarithmic search，是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。

適合的場(chǎng)景：

Sorted（單調(diào)遞增或者遞減）

Bounded （存在上下界，因?yàn)橐环譃槎倪M(jìn)行查找）

Accessible by index（能夠通過索引訪問）

時(shí)間復(fù)雜度：

O(logN)

空間復(fù)雜度:

O(N) 使用常數(shù)空間，無論任何大小的輸入數(shù)據(jù)，算法使用的空間都是一樣的

適用的數(shù)據(jù)結(jié)構(gòu)：

數(shù)組，因?yàn)樵趦?nèi)存中時(shí)連續(xù)的適合使用二分查找。但是鏈表不適合，因?yàn)殒湵碜鴺?biāo)不是固定的，訪問a[2]需要先從a[0]的后繼節(jié)點(diǎn)找到a[1]再通過a[1]的后繼節(jié)點(diǎn)才能訪問到a[2]。

步驟：

初始狀態(tài)left、right 分別指向數(shù)組的頭和尾。

通過(left + right) /2 得到中間位置mid，訪問數(shù)組中mid位置的元素。

判斷其與查找目標(biāo)的大小關(guān)系，相等則程序返回，

比目標(biāo)小則挪動(dòng)left指針到mid + 1；比目標(biāo)大則挪動(dòng)right指針到mid - 1

重復(fù)上面步驟2 ～ 3直到找到目標(biāo)元素或者程序退出。

代碼實(shí)現(xiàn):

參考文章：算法通關(guān)40講

云服務(wù)器 GPU云服務(wù)器二分查找二分查找代碼二分法查找二分查找c語言實(shí)例

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/31333.html

相關(guān)文章

數(shù)據(jù)結(jié)構(gòu)與算法——二分查找

摘要：所以，二分查找較適用于一次排序，多次查找的數(shù)據(jù)。面對(duì)大量的數(shù)據(jù)，二分查找方能體現(xiàn)其優(yōu)勢(shì)。 1. 二分查找的思想二分查找是一種使用十分普遍的查找算法，其基本的思路也非常的簡(jiǎn)單，在一個(gè)有序的數(shù)據(jù)集合中，我們想要查找某個(gè)數(shù)據(jù)，直接取最中間的那個(gè)數(shù)據(jù)，將它和要找的數(shù)據(jù)進(jìn)行比較，如果較大，則在更大的那個(gè)數(shù)值區(qū)間繼續(xù)取中間值查找，反之亦然。例如我們要在一個(gè)有序的集合里[1，3，5，6，7，8，...

boredream 2019-08-16 16:02 評(píng)論0 收藏0
PHP算法之二分查找

摘要：二分查找的定義二分查找也稱折半查找，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。算法的要求從上面的定義我們可以知道，滿足該算法的要求必須如下兩點(diǎn)必須采用順序存儲(chǔ)結(jié)構(gòu)。 showImg(https://segmentfault.com/img/remote/1460000016466416?w=800&h=191); 二分查找的...

Soarkey 2019-07-01 10:44 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握）有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間小）無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序...

zsirfs 2019-08-23 15:33 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握）有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序...

you_De 2019-08-16 15:26 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握）有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間小）無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序...

gotham 2019-07-31 10:07 評(píng)論0 收藏0