二分查找算法速記

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

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

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

適合的場景：

Sorted（單調遞增或者遞減）

Bounded （存在上下界，因為要一分為二的進行查找）

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

時間復雜度：

O(logN)

空間復雜度:

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

適用的數(shù)據(jù)結構：

數(shù)組，因為在內存中時連續(xù)的適合使用二分查找。但是鏈表不適合，因為鏈表坐標不是固定的，訪問a[2]需要先從a[0]的后繼節(jié)點找到a[1]再通過a[1]的后繼節(jié)點才能訪問到a[2]。

步驟：

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

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

判斷其與查找目標的大小關系，相等則程序返回，

比目標小則挪動left指針到mid + 1；比目標大則挪動right指針到mid - 1

重復上面步驟2 ～ 3直到找到目標元素或者程序退出。

代碼實現(xiàn):

參考文章：算法通關40講

GPU云服務器云服務器二分查找二分查找代碼二分法查找二分查找c語言實例

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/31333.html

數(shù)據(jù)結構與算法——二分查找

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

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

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

Soarkey 2019-07-01 10:44 評論0 收藏0
數(shù)據(jù)結構與算法：二分查找

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

zsirfs 2019-08-23 15:33 評論0 收藏0
數(shù)據(jù)結構與算法：二分查找

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

you_De 2019-08-16 15:26 評論0 收藏0
數(shù)據(jù)結構與算法：二分查找

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

gotham 2019-07-31 10:07 評論0 收藏0