今天主要跟大家分享二分查找算法。

有興趣的朋友的可以去閱讀《算法圖解》這本書。

首先說(shuō)下什么是算法。

算法定義：

一組完成任務(wù)的指令。任何的代碼片段都可視為算法。

算法的優(yōu)缺點(diǎn)：

不同的算法，性能高低不同。

算法的作用：

解決問(wèn)題的技巧。不同的問(wèn)題，可以選擇不同解決方式。

二分查找法：

定義:在一個(gè)有序的元素列表中，查找元素是否包含在列表，或者是具體在某個(gè)索引位置。

EX:

例如我們要在100個(gè)有序的數(shù)組中，找到40這個(gè)數(shù)，那么在數(shù)組的哪個(gè)位置呢？

笨方法:一個(gè)挨著一個(gè)的找。找100次就找到了。

好方法：折半查找,首先找出整個(gè)數(shù)組中的中位數(shù)和要查找的數(shù)，做比較。

分為兩堆，一堆大數(shù)，一堆小數(shù)。如果中間數(shù)<查找數(shù)，那么就從大數(shù)堆里去找。

再把大數(shù)堆分為兩堆，以此類推。就最終能到找到，你要找的數(shù)。

圖片來(lái)自《算法圖解》

代碼如下：

說(shuō)到算法，接下來(lái)就得說(shuō)下“大O表示法”。

大O表示法 是一種特殊的表示法，指出了算法的速度有多快。

之前提到笨方法，就是線性時(shí)間 O(n) , n:表示操作數(shù)。

二分查找法，就是對(duì)數(shù)時(shí)間 O(logn)。查找100個(gè)數(shù)的數(shù)組，最多只要7次。

(log^100,log指的是log2,log2^100相當(dāng)于問(wèn)“將多少個(gè)2相乘的結(jié)果為100”)

如果忘了對(duì)數(shù)是什么？請(qǐng)自行百度一下。由于不是這次主要內(nèi)容，這里就不展開介紹。

今天，就給大家分享到這。明天會(huì)繼續(xù)分享《選擇排序+數(shù)組和鏈表》。

PS:

如果你閱讀之后，有所收獲。請(qǐng)記得點(diǎn)贊哦。o(*￣︶￣*)o。你的支持將是我寫作的動(dòng)力。