級(jí)別： ★☆☆☆☆
標(biāo)簽：「算法」「二分查找」「大O表示法」
作者： MrLiuQ
審校： QiShare團(tuán)隊(duì)

前言：最近小編在看《算法圖解》，將會(huì)總結(jié)一系列算法相關(guān)的文章。
關(guān)于算法的系列文章，小編將準(zhǔn)備分“三步”來編寫：

• 第一步：描述算法，并提供“圖解”及示例Demo。
• 第二步：用大O表示法討論運(yùn)行時(shí)間。
• 第三步：分析該算法能解決的實(shí)際問題。
  （PS：示例代碼將基于Python編寫）

本篇將介紹二分查找與大O表示法，并為后續(xù)的算法文章打下算法基礎(chǔ)。

一、算法簡介

算法，簡單來說，就是一組完成任務(wù)的指令。任何代碼片段都可視為算法。

算法的用途主要有兩個(gè)方面：

• 一：提高代碼的運(yùn)行速度，優(yōu)化業(yè)務(wù)邏輯。 => 已達(dá)到提高代碼質(zhì)量的目的。
• 二：解決實(shí)際應(yīng)用問題。 => 已達(dá)到完成業(yè)務(wù)需求的目的。

二、二分查找

問題：假設(shè)有一個(gè)有序數(shù)組（前提：有序數(shù)組），我們要查詢一個(gè)數(shù)在這個(gè)數(shù)組中的位置（index），我們應(yīng)該如何查找？

先介紹一個(gè)簡單而暴力的查找方式：直接遍歷一遍這個(gè)數(shù)組，找到對(duì)應(yīng)的數(shù)后再返回index。這個(gè)方法我們稱之為——簡單查找。

2.1 簡單查找：

直接遍歷數(shù)組查找元素。很簡單很暴力。

基于Python的算法：

def easy_search(list, item):
    for index in range(len(list)):
        if list[index] == item:
            return index
    return None

測評(píng)：
簡單查找在運(yùn)氣好時(shí)（即遍歷的第一個(gè)元素即為該數(shù)），只需要查找一次。
但是當(dāng)如果所找元素在數(shù)組末尾時(shí)，就要一直遍歷到最后一個(gè)元素才能找到那個(gè)數(shù)。n個(gè)元素的數(shù)組要找n次。

這顯然效率會(huì)不高，這時(shí)候我們可以使用：二分查找法。

2.2 二分查找：

二分查找，顧名思義，每次查找將數(shù)組分成兩部分，從中間開始找。

• 如果發(fā)現(xiàn)數(shù)比中間數(shù)大，即數(shù)在中間數(shù)與最大數(shù)之間，就修改low的值。再對(duì)比中間值。
• 如果發(fā)現(xiàn)數(shù)比中間數(shù)小，即數(shù)在最小數(shù)與中間數(shù)之間，就修改high的值。再對(duì)比中間值。

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表示法

時(shí)間復(fù)雜度由大O表示法描述。

• 時(shí)間復(fù)雜度描述的是算法的運(yùn)行效率；
• 時(shí)間復(fù)雜度指的并非具體時(shí)間，而是操作數(shù)的增速。

運(yùn)用簡單查找算法，在n個(gè)元素的數(shù)組中查找一個(gè)數(shù)，情況最遭時(shí)，需要n步，所以簡單查找的時(shí)間復(fù)雜度是O(n)；

運(yùn)用二分查找算法，在n個(gè)元素的數(shù)組中查找一個(gè)數(shù)，情況最遭時(shí)，需要(log n)步，所以二分查找的時(shí)間復(fù)雜度是O(log n)。

工程源碼：QiAlgorithms

推薦文章：
iOS 自定義拖拽式控件：QiDragView
iOS 自定義卡片式控件：QiCardView
iOS Wireshark抓包
iOS Charles抓包
初探TCP
IP、UDP初探