面試向算法 - 二分法專題(一)

2021-02-21 百學原理
前言

在我看來，大部分面試的算法題從來都不是難在思維，而是缺乏系統的教學。它不像數學屬於普及的基礎教育，算法題目的大部分知識、技巧往往都局限於 competitive programming 當中 (比如各種 OI 競賽、 ACM 競賽等)，這些都是大部分計算機行業從業者接觸不到的。它就像一個大群體中一個半封閉的小群體一樣，系統的知識就在那裡，只是我們很少會主動走進去。因此，我期望將這些知識給帶出來，就引申出了本系列文章和視頻。

二分法是一種隨處可見卻又非常精妙的算法，我們最熟知的用法是在一個有序數組中查找某個 target 是否存在。初學二分法的同學可能會被各種邊界情況、不同寫法、是開區間還是閉區間等細節弄糊塗，以至於捨本逐末。其實並不需要如此，我們只需要記住一種最方便的寫法並理解它即可。

二分法主題分為兩篇，本篇為第一篇。共涉及到 60 道 題目，以 LeetCode 難度劃分屬於 hard 和 medium 偏上的題目。

注意：搭配 B 站視頻更香奧！

正文

通常我們將二分法分為整數域上的二分和實數域上的二分。

整數二分的細節在於終止邊界、左右區間取捨時的開閉情況，來避免漏掉答案或者造成死循環。

因此，本文會分別給出 整數二分 和 實數二分 的模板，來幫助大家解決 90% 以上的廣泛二分問題。廣泛二分問題指的是如下幾種類型：

最大/最小平均值(max/min average)

理解了這幾種題型，也就能夠理解接近 100 道的算法題，基本都是 leetcode hard/medium 級別的。

在給出模板之前，我們得先理解什麼是二分？

二分不等價於序列上的單調性。它的本質是：

如果我們能夠通過某種特性將一個區間劃分成兩個區間，左邊區間滿足某種特性；右邊區間不滿足某種特性。那麼我們就能夠通過二分法來尋找左區間的右端點或者右區間的左端點。換句話講，有單調性一定可以二分，但是二分不一定要有單調性。

更多細節可以在 B 站搜索 《百學原理》 up主，面試向算法系列 - 1.4 二分法的經典應用

（圖 4-1）

整數二分模板
def binary_search(l , r): # 模板一：尋找右區間的左端點(上圖紅色部分)

    while l < r:
        mid = (l+r)//2 # 注意 l+r

        if check(mid): r = mid
        else: l = mid+1
def binary_search(l , r): # 模板二：尋找左區間的右端點（上圖藍色部分）

    while l < r:
        mid = (l+r+1)//2 # 注意 l+r+1

        if check(mid): l = mid
        else: r = mid-1
整數二分為什麼會有兩個模板？
這是為了方便構造 check() 方法和對答案的求解。
我們來看 leetcode: 34. 在排序數組中查找元素的第一個和最後一個位置（題目視頻中有詳細講解）[1]。
給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。你的算法時間複雜度必須是 O(log n) 級別。
如果數組中不存在目標值，返回 [-1, -1]。
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
示例 2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]
如何尋找 target 在數組中的開始位置呢？
很明顯，由於從 開始位置往後 所有的值都是 
def check(x):
    return x >= target
也就是我們通過上述 check() 方法將數組劃分為兩個區間，開始位置就是右區間的左端點(也就是模板一)，如下圖 4-2。
（圖 4-2）
那麼，我們是否可以用 模板二 求解開始位置呢？很顯然也是可以的，只是會麻煩一些，如圖 4-2 中的 4。我們可以通過 x < target 求得左區間的右端點，也就是最後一個 < target 的位置，假設為 i，那麼 i+1 顯然就是 target 的起始位置(這裡不考慮不存在情況)。
因此，我們可以得出一個結論：模板一 和 模板二 都可以得出具體解，只是在面對不同問題時哪個更加方便而已。
那麼該如何求解結束位置呢？
這個時候使用 模板二 就更加方便了，如圖 4-2 中的 3 所示，我們只要構造 check() 為 x <= target 即可。
下面我們來看模板的細節，一個很重要的點是：
模板一：mid = (l+r)//2; r = mid; l = mid+1模板二：mid = (l+r+1)//2; l = mid; r = mid+1
為什麼要這樣寫呢？
這兩種寫法都是在解決同一個問題 - 避免範圍縮小到 2 時，產生死循環
為什麼改變寫法就有可能產生死循環呢？ 其實舉個反例即可。
本身 模板一就是為了獲得右區間的左端點，所以  r = mid 和 l = mid+1是肯定的，大家記住即可。那麼如果模板一變成 mid = (l+r+1)//2，也就是在 [i, i+1] 時， mid = i+1. 可能會產生如下圖所示的情況：
(圖 4-3)
模板二的證明和模板一類似。
下面我們來看下模板一和模板二是如何運用在基礎題目裡面的（以下所有題目在 B站 1.4.1 和 1.4.2 中都有詳細講解）
（圖 4-4）
題目問的是 - 是否存在目標值，所以套用模板一和模板二都可以。稍微有點變形的是題目給出的序列是二維的，因此我們需要通過簡單的變形將二維轉為一維。
l = 0
r = m * n - 1

while l < r:
    mid = (l+r)//2
    row = mid // n
    col = mid % n 
    if matrix[row][col] >= target: r = mid
    else: l = mid+1

if matrix[l//n][l%n] == target: return True
else: return False
leetcode: 153. 尋找旋轉排序數組中的最小值[3]
假設按照升序排序的數組在預先未知的某個點上進行了旋轉。( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。請找出其中最小的元素。你可以假設數組中不存在重複元素。
（圖 4-5）
如上圖所示，可以直接根據模板一構造出 check() 方法（代碼就不給了）。
如果允許重複值呢？比如 leetcode: 154. 尋找旋轉排序數組中的最小值 II[4]
其實重複值只是迷惑了我們的眼睛，儘管在判斷到重複時（出現 check(mid) == nums[r]），我們無法劃分區間。但是很顯然，去掉其中一個不會對我們最終的結果產生影響，所以我們只需要 r-- 即可。
l = 0
r = n-1

while l < r:
    mid = (l+r)//2

    if nums[mid] == nums[r]:
        r -= 1
    elif nums[mid] > nums[r]:
        l = mid + 1
    else:
        r = mid

return nums[l]
按照這種做法，leetcode: 81. 搜索旋轉排序數組 II[5] 的解法也就顯而易見了。
除了完成上述題目，還有一些其他題目大家可以嘗試：
leetcode: 275. H 指數 II[7]實數二分模板
binary_search(l , r): // 尋找結果

    eps = 1e-6
    while r - l >= eps:
        mid = (l+r) / 2

        if check(mid): r = mid
        else: l = mid
實數二分不會存在整數二分的細節問題，只需要注意精度問題即可。至於具體原因，大家簡單畫個圖即可，或者類比於微積分，當兩個點無限接近時，我們就認為其在無限小時是一個點。
實數二分最常見的例子就是：
二分法求三次方根 acwing: 790. 數的三次方根[9]
具體代碼我就不給了，想要更詳細的過程可以看 B 站視頻 1.4.1 和 1.4.2
課後習題
acwing: 696. 哈默隊長(Google Kickstart2013 Practice Round Problem B)[10]總結 
剩下的 4 種經典應用請看下篇。
參考資料[1]
leetcode: 34. 在排序數組中查找元素的第一個和最後一個位置（題目視頻中有詳細講解）: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[2]
leetcode: 74. 搜索二維矩陣: https://leetcode-cn.com/problems/search-a-2d-matrix/
[3]
leetcode: 153. 尋找旋轉排序數組中的最小值: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
[4]
leetcode: 154. 尋找旋轉排序數組中的最小值 II: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
[5]
leetcode: 81. 搜索旋轉排序數組 II: https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
[6]
leetcode: 162. 尋找峰值: https://leetcode-cn.com/problems/find-peak-element/
[7]
leetcode: 275. H 指數 II: https://leetcode-cn.com/problems/h-index-ii/
[8]
codeforces edu 4 道題目: https://codeforces.com/edu/course/2/lesson/6/1/practice
[9]
acwing: 790. 數的三次方根: https://www.acwing.com/problem/content/792/
[10]
acwing: 696. 哈默隊長(Google Kickstart2013 Practice Round Problem B): https://www.acwing.com/problem/content/description/698/

相關焦點

  • 面試向算法 - 二分法專題(二)
    前言 在我看來，大部分面試的算法題從來都不是難在思維，而是缺乏系統的教學。它不像數學屬於普及的基礎教育，算法題目的大部分知識、技巧往往都局限於 competitive programming 當中 (比如各種 OI 競賽、 ACM 競賽等)，這些都是大部分計算機行業從業者接觸不到的。它就像一個大群體中一個半封閉的小群體一樣，系統的知識就在那裡，只是我們很少會主動走進去。
  • 面試手撕算法系列:二分法
    最近春招開始了，面試面著面著一言不合就開始手撕代碼手撕就手撕，接下來我打算寫幾個專題講講面試中手撕的常見題目 這些都是LeetCode上有的題目 手撕無非就是 樹、鍊表、二分、字符串這些常用的數據結構二分法查找，也稱為折半法，是一種在有序數組中查找特定元素的搜索算法。
  • 算法競賽小專題系列(1):二分法、三分法
    清華大學出版社二分法和三分法是算法競賽中常見的算法思路，本文介紹了它們的理論背景、模板代碼、典型題目。1. 二分法的理論背景在《計算方法》教材中，關於非線性方程的求根問題，有一種是二分法。所以，二分法的複雜度是O(logn)的。例如，如果函數在區間[0, 100000]內單調變化，要求根的精度是10-8，那麼二分次數是44次。　　二分非常高效。所以，如果問題是單調性的，且求解精確解的難度很高，可以考慮用二分法。　　在算法競賽題目中，有兩種題型：整數二分、實數二分。
  • 遍歷,二分法:排序,紅黑樹,斯特拉森算法
    幾個「最」，說明人對極值更敏感:(電腦一般情況下，要麼從頭到尾遍歷，要麼使用二分法。電腦算法的優化，很多就是把遍歷算法變成二分法的遞歸。典型的遍歷算法，遍歷兩遍，複雜度為O(N^2)。歸併排序，則是典型的二分法。16個數，一分為二每組8個，二分為4每組4個，三分為8每組2個，四分為16每組1個。每組1個的時候也就無所謂順序了。
  • 電面跪在follow up,算法面試難度又升了?
    而根據前線面試小夥伴的消息，現在的算法面試似乎越來越難了。像Uber、Lyft、Pinterest 這種剛 IPO 的公司喜歡出難題就不說了，連 FLAG 這樣的大廠也是變種題和 follow up 層出不窮。
  • 二分法
    二分法是什麼呢？百度上的定義是：「對於區間[a,b]上連續不斷且f(a)·f(b)<0的函數y=f(x)，通過不斷地把函數f(x)的零點所在的區間一分為二，使區間的兩個端點逐步逼近零點，進而得到零點近似值的方法叫二分法。」        這個定義比較複雜，我們把它分成幾部分來看。
  • 算法工程師面試前需掌握的18大面試題!
    【IT168 評論】算法是比較複雜又基礎的學科，每個學編程的人都會學習大量的算法。而根據統計，以下這18個問題是面試中最容易遇到的，本文給出了一些基本答案，供算法方向工程師或對此感興趣的程式設計師參考。1)請簡單解釋算法是什麼?
  • 程式設計師面試題,200億個數字找中位數,不給分桶算法,怎麼辦?
    海量數據裡面如何尋找一堆數字的中位數，是一道非常常見的面試題。據稱，這個題目是騰訊前首席技術執行官Tony推崇的一個面試題，被加入的騰訊的面試題題庫。我們最常見的做法便是分桶算法了。什麼是分桶算法呢？什麼是分桶呢？就是把若干的數字分到一個桶裡面，對外界來說，只關心桶編號。
  • 「二分法」中數學思想的提煉
    ，經歷求近似解的過程，總結出「二分法」的一般程序．「人猜對」對應著方程的根……，就是解了一道數學題.學生在這個數學活動中，學到了二分法，看到連續函數的應用，感悟了「函數與方程的數學思想」，「近似逼近的數學思想」，「數形結合的數學思想」，「特殊與一般的數學思想」，「程序化地處理問題的算法思想」等，經歷了數學化的提煉過程，就是在學習解題，就是在通過學習數學去學會思維．（不要誤解，上課的前半段講概念、證定理沒有解題，後半段才有解題）
  • 九章算法班 | 贏秋招免費內推, 一個月搞定面試算法!
    簡直太坑爹為了應對最新的面試九章算法全面搜集最新面經研究最新面試套路升級推出《九章算法班V5.0》文末可獲取《2018最新面試熱點、套路總結》PPT算法題目千千萬《九章算法V5.0》配套最新 LintCode OJ 題庫。根據最新的面經對配套作業題進行了大換血，在面試中遇到原題的概率更高了。
  • 九章算法班 | 1個月搞定面試算法,更有內推等著你
    簡直太坑爹為了應對最新的面試九章算法全面搜集最新面經研究最新面試套路升級推出《九章算法班V5.0》文末可獲取《2018最新面試熱點、套路總結》PPT算法題目千千萬2018年算法面試的考法越來越靈活多變，有些公司甚至要求面試者寫出非最優算法，這對於面試者來說提出了更高的要求。此外，2018年面試的知識點考察也不同於往年。
  • 漫畫:二分法深度剖析(第二講)
    今天是小浩算法「365刷題計劃」第67天。繼續為大家分享二分法系列篇的內容，看一道比較簡單的題目。這道題目是比較簡單，但我認為同時也是非常經典，建議大家掌握！PS：建議大家停留個兩分鐘先想一想...直接拉下去看題解就沒什麼意思了。
  • 同樣是考算法,FLAG面試官都關注什麼?
    9月即將迎來秋招面試高峰期，對於目標是FLAG的同學來說，刷題是極為重要的面試基礎。除了埋頭刷題，無論是找實習還是找全職，都有必要了解FLAG算法面試的難度和風格。 Facebook的算法題有題庫，但比較難預測。
  • 憑FB大神筆記秒了Google的算法題
    Ray同學就是這份筆記的受益者之一，今年秋招他準備的晚，離面試剩一個多月時還只能刷easy題，一上medium就卡殼。令狐老師刷題超過3000+，他總結出的模板和套路屬於高濃縮的「精華」，比如這個二分法的模板👇除了二分法，令狐老師還整理了排序算法Sorting、雙指針、BFS、DFS
  • 免費 ML 算法面試大全,GitHub 上破萬星
    在本項目中，作者 imhuay 為大家準備了 ML 算法工程師面試指南，它提供了完整的面試知識點、編程題及題解、各科技公司的面試題錦等內容。目前該 GitHub 項目已經有 1 萬+的收藏量，想要跳一跳的同學快來試試吧。如下所示為整個項目的結構，其中從機器學習到數學主要提供的是筆記與面試知識點，讀者可回顧整體的知識架構。
  • 二分法題型小結
    學好算法沒有捷徑，最好的捷徑就是多刷題，並且跳出舒適區，每道題都要尋找最優解，也不能老是做那些你自己比較擅長的題，不定期更新 Leetcode 的題，每道題都會給出多種解法以及最優解在刷題的過程中，二分法用的還是挺多的，有時候超時了往往是你沒有用上二分法，今天我就來稍微總結下用的最多的三種二分法搜索。
  • 二分法其實很簡單,為什麼老是寫不對!!
    作者丨代碼隨想錄 來源丨代碼隨想錄 （code_thinking）相信很多人對二分法是又愛又恨，愛是在於它思想簡單
  • 諸葛亮的二分法遊戲
    二分法是數學裡非常經典的方法,不管是初等數學,高等數學,計算數學,幾乎都有他的影子，學計算機的朋友就更不會陌生。
  • 字節大佬Leetcode刷題筆記,看完吊打問你算法的面試官
    第四部分是每日一題，每日一題是在交流群（包括微信和 qq）裡進行的一種活動，大家一起 解一道題，這樣討論問題更加集中，會得到更多的反饋。而且 這些題目可以被記錄下來，日後會進行篩選添加到倉庫的題解模塊。
  • 新一波春招來襲,你可能需要這份GitHub萬星的ML算法面試大全
    在本項目中，作者為大家準備了 ML 算法工程師面試指南，它提供了完整的面試知識點、編程題及題解、各科技公司的面試題錦等內容。目前該 GitHub 項目已經有 1 萬+的收藏量，想要跳一跳的同學快來試試吧。如下所示為整個項目的結構，其中從機器學習到數學主要提供的是筆記與面試知識點，讀者可回顧整體的知識架構。