前兩天去公司應(yīng)聘搀捷，還沒等我開始自我介紹，面試官上來就要手撕代碼勉耀。題目是這樣的 :
給定一個排序數(shù)組和一個目標值指煎，在數(shù)組中找到目標值蹋偏，并返回其索引便斥。如果目標值不存在于數(shù)組中至壤，返回它將會被按順序插入的位置。
請必須使用時間復(fù)雜度為 O(log n) 的算法枢纠。
示例：
輸入: nums = [1,3,5,6], target = 5
輸出: 2
題目雖然雖然很基礎(chǔ)像街，但是要求時間復(fù)雜度為 O(log n) 。那么肯定就得用二分查找的方法去做了晋渺，下面就用漫畫圖解的形式帶大家一起回顧一下二分查找镰绎。
二分查找
下面的示例說明了二分查找的工作原理。我隨便想一個1~100的數(shù)字木西。
你的目標是以最少的次數(shù)猜到這個數(shù)字畴栖。你每次猜測后，我會說小了八千、大了或?qū)α恕?br>
假設(shè)你從1開始依次往上猜吗讶，猜測過程會是這樣。
這是簡單查找恋捆，更準確的說法是傻找照皆。每次猜測都只能排除一個數(shù)字。如果我想的數(shù)字是99沸停，你得猜99次才能猜到膜毁！
更佳的查找方式
下面是一種更佳的猜法。從 50 開始愤钾。
小了瘟滨，但排除了一半的數(shù)字！至此能颁，你知道1～50都小了室奏。接下來，你猜 75劲装。
大了胧沫，那余下的數(shù)字又排除了一半！使用二分查找時占业，你猜測的是中間的數(shù)字绒怨，從而每次都將余下的數(shù)字排除一半。接下來谦疾，你猜 63（50和75中間的數(shù)字）南蹂。
這就是二分查找，你學(xué)習(xí)了第一種算法念恍！每次猜測排除的數(shù)字個數(shù)如下六剥。
不管我心里想的是哪個數(shù)字晚顷，你在 7 次之內(nèi)都能猜到，因為每次猜測都將排除很多數(shù)字疗疟！
假設(shè)你要在字典中查找一個單詞该默，而該字典包含 240 000 個單詞，你認為每種查找最多需要多少步策彤？
如果要查找的單詞位于字典末尾栓袖，使用簡單查找將需要 240 000 步。使用二分查找時店诗，每次排除一半單詞裹刮，直到最后只剩下一個單詞。
因此庞瘸，使用二分查找只需 18 步——少多了捧弃！一般而言，對于包含n個元素的列表擦囊，用二分查找最多需要 log2n 步违霞，而簡單查找最多需要 n 步。
算法樣例
下面來看看如何編寫執(zhí)行二分查找的Python代碼霜第。這里的代碼示例使用了數(shù)組葛家。如果你不熟悉數(shù)組，也不用擔(dān)心泌类。你只需知道癞谒，可將一系列元素存儲在一系列相鄰的桶（bucket），即數(shù)組中刃榨。這些桶從0開始編號：第一個桶的位置為#0弹砚，第二個桶為#1，第三個桶為#2枢希，以此類推桌吃。
函數(shù)binary_search接受一個有序數(shù)組和一個元素。如果指定的元素包含在數(shù)組中苞轿，這個函數(shù)將返回其位置茅诱。你將跟蹤要在其中查找的數(shù)組部分——開始時為整個數(shù)組。
你每次都檢查中間的元素搬卒。
如果猜的數(shù)字小了瑟俭，就相應(yīng)地修改low。
如果猜的數(shù)字大了契邀，就修改high摆寄。完整的代碼如下。
def binary_search(list, item):
# low和high用于跟蹤要在其中查找的列表部分
low = 0
high = len(list) - 1
# 只要范圍沒有縮小到只包含一個元素
while low <= high:
mid = (low + high) // 2 # 檢查中間的元素
guess = list[mid]
if guess == item: # 找到了元素
return mid
if guess > item: # 猜的數(shù)字大了
high = mid - 1
else: # 猜的數(shù)字小了
low = mid + 1
return None # 沒有指定的元素
回到面試題
給定一個排序數(shù)組和一個目標值，在數(shù)組中找到目標值微饥，并返回其索引逗扒。如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置欠橘。
請必須使用時間復(fù)雜度為 O(log n) 的算法矩肩。
輸入: nums = [1,3,5,6], target = 5
輸出: 2
那么針對這道題，直接套用二分法即可简软，即不斷用二分法逼近查找第一個大于等于target的下標 蛮拔。我們寫出的二分查找算法就是這樣的：
def searchInsert(nums, target):
left, right = 0, len(nums)
while (left < right):
# 下面這樣寫是考慮大數(shù)情況下避免溢出
mid = (right - left) // 2 + left
if target <= nums[mid]:
right = mid
else:
left = mid + 1
return left
算法學(xué)習(xí)心得
相信大家通過上面這種圖解的方式很輕松就能掌握二分查找的原理述暂。這是《算法圖解》中的一個例子痹升，這是一本能夠像小說一樣有趣的算法入門書。
除了二分查找以外畦韭，本書還介紹了選擇排序疼蛾、遞歸、快速排序艺配、散列表察郁、廣度優(yōu)先搜索、狄克斯特拉算法转唉、貪婪算法皮钠、動態(tài)規(guī)劃、K最近鄰算法等赠法。本書所有的示例代碼都是使用Python 2.7編寫的麦轰。書中在列出代碼時使用了等寬字體。有些代碼還進行了標注砖织，旨在突出重要的概念款侵。
如果你是剛?cè)腴T的同學(xué)，非常建議從類似這樣的簡單算法書開始學(xué)習(xí)侧纯，切記不要一上來就像一口吃個胖子新锈，路還是得一步一步走。
如果你覺得這本書過于簡單眶熬，還可以看一下普林斯頓算法紅寶書《算法》妹笆，這本書是風(fēng)靡全世界近 40 年的算法經(jīng)典。很多大學(xué)都拿它當(dāng)作教材娜氏，該書非常系統(tǒng)拳缠、全面、嚴謹牍白，提供了實際代碼脊凰，而且這些 Java 代碼實現(xiàn)采用了模塊化的編程風(fēng)格，讀者可以方便地加以改造。
除了看書以外狸涌，還應(yīng)該加上實戰(zhàn)練手切省。在具備一定的算法基礎(chǔ)以后，就可以上leetcode開始刷題了帕胆。我是按照某一類別的題型朝捆，由易到難，循序漸進懒豹，以此來鞏固對算法的理解芙盘，并且提高自己的編程能力。
最后再送給大家一句 Linux 的創(chuàng)始人 Linus Torvalds 的話脸秽，“Talk is cheap. Show me the code.”
