前言：最近小編在看《算法圖解》邓了，將會總結(jié)一系列算法相關(guān)的文章庞钢。
關(guān)于算法的系列文章瞳购，小編將準(zhǔn)備分“三步”來編寫：
- 第一步：描述算法，并提供“圖解”及示例Demo玖绿。
- 第二步：用大O表示法討論運(yùn)行時間敛瓷。
- 第三步：分析該算法能解決的實際問題。
（PS：示例代碼將基于Python編寫）
本篇將介紹二分查找與大O表示法琐驴，并為后續(xù)的算法文章打下算法基礎(chǔ)。
一绝淡、算法簡介
算法苍姜，簡單來說牢酵，就是一組完成任務(wù)的指令。任何代碼片段都可視為算法衙猪。
算法的用途主要有兩個方面：
- 一：提高代碼的運(yùn)行速度馍乙，優(yōu)化業(yè)務(wù)邏輯垫释。 => 已達(dá)到提高代碼質(zhì)量的目的。
- 二：解決實際應(yīng)用問題棵譬。 => 已達(dá)到完成業(yè)務(wù)需求的目的显蝌。
| 算法的用途 | 目的 |
|---|---|
| 提高代碼運(yùn)行速度，優(yōu)化業(yè)務(wù)邏輯 | 提高代碼質(zhì)量 |
| 解決實際應(yīng)用問題 | 完成業(yè)務(wù)需求 |
二订咸、二分查找
問題：假設(shè)有一個有序數(shù)組（前提：有序數(shù)組）曼尊，我們要查詢一個數(shù)在這個數(shù)組中的位置（index）脏嚷，我們應(yīng)該如何查找？
先介紹一個簡單而暴力的查找方式：直接遍歷一遍這個數(shù)組神郊，找到對應(yīng)的數(shù)后再返回index高每。這個方法我們稱之為——簡單查找屿岂。
2.1 簡單查找：
直接遍歷數(shù)組查找元素鲸匿。很簡單很暴力阻肩。
基于Python的算法：
def easy_search(list, item):
for index in range(len(list)):
if list[index] == item:
return index
return None
測評：
簡單查找在運(yùn)氣好時（即遍歷的第一個元素即為該數(shù)）运授，只需要查找一次乔煞。
但是當(dāng)如果所找元素在數(shù)組末尾時，就要一直遍歷到最后一個元素才能找到那個數(shù)逗宜。n個元素的數(shù)組要找n次空骚。
這顯然效率會不高，這時候我們可以使用：二分查找法囤屹。
2.2 二分查找：
二分查找，顧名思義乡括，每次查找將數(shù)組分成兩部分智厌，從中間開始找诲泌。
- 如果發(fā)現(xiàn)數(shù)比中間數(shù)大铣鹏，即數(shù)在中間數(shù)與最大數(shù)之間，就修改
low的值呻澜。再對比中間值惨险。 - 如果發(fā)現(xiàn)數(shù)比中間數(shù)小，即數(shù)在最小數(shù)與中間數(shù)之間辫愉，就修改
high的值。再對比中間值屏镊。
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) / 2
if list[mid] == item:
return mid
if list[mid] > item:
high = mid - 1
else:
low = mid + 1
return None
這樣痰腮，每次循環(huán)就能舍去一半的元素，大大提高了查找的效率棍丐。這就是二分查找法。
三歌逢、大O表示法
時間復(fù)雜度由大O表示法描述。
- 時間復(fù)雜度描述的是算法的運(yùn)行效率砰苍；
- 時間復(fù)雜度指的并非具體時間阱高，而是操作數(shù)的增速。
運(yùn)用簡單查找算法讨惩，在n個元素的數(shù)組中查找一個數(shù)，情況最遭時荐捻，需要n步，所以簡單查找的時間復(fù)雜度是O(n)厂置；
運(yùn)用二分查找算法魂角，在n個元素的數(shù)組中查找一個數(shù)，情況最遭時野揪，需要(log n)步，所以二分查找的時間復(fù)雜度是O(log n)海铆。
工程源碼：QiAlgorithms
