1. 項(xiàng)目概述為什么二分查找值得你花時(shí)間如果你刷過算法題或者在工作中處理過有序數(shù)據(jù)大概率聽過“二分查找”這個(gè)名字。它聽起來簡(jiǎn)單但真正能把它寫對(duì)、寫穩(wěn)、寫快的人遠(yuǎn)沒有想象中多。我見過太多人包括我自己早期在邊界條件上栽跟頭不是死循環(huán)就是漏掉元素一個(gè)簡(jiǎn)單的while (left right)和while (left right)就能把人繞暈。今天我們不談那些高深莫測(cè)的理論就從一個(gè)一線開發(fā)者的視角徹底拆解二分查找并給你一個(gè)經(jīng)過大量實(shí)戰(zhàn)檢驗(yàn)、幾乎能覆蓋所有場(chǎng)景的“萬(wàn)能模板”。這個(gè)模板不是魔法而是對(duì)二分查找本質(zhì)理解的結(jié)晶它能幫你把思考重心從“邊界怎么寫”轉(zhuǎn)移到“問題本身怎么解”上。簡(jiǎn)單說二分查找是一種在有序集合中快速定位目標(biāo)值的算法。它的核心思想是“分而治之”每次比較中間元素根據(jù)比較結(jié)果將搜索范圍縮小一半。時(shí)間復(fù)雜度是O(log n)這意味著對(duì)于一個(gè)有10億個(gè)元素的有序數(shù)組你最多只需要比較30次左右就能找到答案效率極高。無論是面試中的高頻考點(diǎn)還是實(shí)際開發(fā)中處理日志時(shí)間戳、用戶ID范圍、配置表查詢等場(chǎng)景二分查找都是你必須熟練掌握的基本功。本文適合所有正在學(xué)習(xí)算法、準(zhǔn)備技術(shù)面試或希望優(yōu)化代碼中查找邏輯的開發(fā)者。我們將從最基礎(chǔ)的原理講起一步步推導(dǎo)出那個(gè)“萬(wàn)能模板”并通過多個(gè)變種問題讓你真正掌握其精髓。2. 二分查找的核心思想與“坑點(diǎn)”全解析2.1 算法本質(zhì)不只是“找數(shù)字”很多人對(duì)二分查找的理解停留在“在一個(gè)有序數(shù)組里找一個(gè)數(shù)”。這沒錯(cuò)但太片面了。二分查找更本質(zhì)的是一種基于“有序性”和“單調(diào)性”進(jìn)行快速?zèng)Q策的框架。這里的“有序”不一定是數(shù)字大小可以是任何滿足單調(diào)關(guān)系的屬性比如時(shí)間先后、版本號(hào)大小、任務(wù)優(yōu)先級(jí)等。算法利用這種單調(diào)性通過一次比較就能果斷地拋棄一半不可能存在答案的搜索空間。舉個(gè)例子想象你在翻一本厚厚的字典找單詞。你不會(huì)從第一頁(yè)開始一頁(yè)頁(yè)翻而是先打開中間一頁(yè)看看上面的單詞。如果你要找的單詞按字母序在這頁(yè)單詞之后那么前半本書就可以完全不用看了反之亦然。你不斷重復(fù)這個(gè)過程每次都能扔掉一半的頁(yè)數(shù)。這就是二分查找最直觀的體現(xiàn)。2.2 那些年我們踩過的“邊界”之坑二分查找的代碼框架看似簡(jiǎn)單但細(xì)節(jié)是魔鬼。幾乎所有錯(cuò)誤都集中在循環(huán)條件和邊界更新上。下面我羅列幾個(gè)最常見的“坑”你看看自己中過幾個(gè)循環(huán)條件不清晰到底用while (left right)還是while (left right)這是第一個(gè)分水嶺。前者對(duì)應(yīng)的搜索區(qū)間是閉區(qū)間[left, right]后者是左閉右開區(qū)間[left, right)。選擇不同后續(xù)的邊界更新和返回值處理就完全不同。中間值計(jì)算溢出計(jì)算中間索引時(shí)很多人會(huì)寫mid (left right) / 2。這在left和right都是很大的整數(shù)時(shí)left right可能會(huì)超出整型范圍導(dǎo)致溢出。正確的寫法是mid left (right - left) / 2。邊界更新死循環(huán)在while (left right)的框架下如果你在目標(biāo)值大于中間值時(shí)執(zhí)行l(wèi)eft mid而在某些情況下mid的計(jì)算結(jié)果始終等于left那么left就永遠(yuǎn)不會(huì)更新導(dǎo)致死循環(huán)。例如left 3, right 4時(shí)mid 3如果條件分支讓left mid則left還是3陷入無限循環(huán)。返回值意義混淆循環(huán)結(jié)束后left和right指向哪里是目標(biāo)值的位置還是第一個(gè)大于目標(biāo)值的位置或者是插入位置如果不清楚循環(huán)不變量的意義根本無法確定返回哪個(gè)變量。這些坑的根源在于沒有明確定義搜索區(qū)間和循環(huán)不變量。接下來我們就從這兩個(gè)核心概念出發(fā)構(gòu)建一個(gè)牢固的思維框架。3. 構(gòu)建思維基石搜索區(qū)間與循環(huán)不變量3.1 明確你的“搜索空間”兩種區(qū)間定義在動(dòng)筆寫代碼之前你必須先想清楚你定義的left和right初始值代表的是一個(gè)什么樣的區(qū)間這個(gè)區(qū)間在整個(gè)循環(huán)過程中需要始終保持一個(gè)不變的性質(zhì)循環(huán)不變量。第一種閉區(qū)間[left, right]定義left和right都指向有效的、可能包含答案的索引。初始化left 0,right nums.length - 1。循環(huán)條件while (left right)。因?yàn)楫?dāng)left right時(shí)區(qū)間[left, right]仍然包含一個(gè)元素有必要進(jìn)行最后一次檢查。邊界更新如果nums[mid] target說明目標(biāo)值只可能在右邊且mid本身已經(jīng)檢查過不是目標(biāo)所以新的左邊界是mid 1。如果nums[mid] target說明目標(biāo)值只可能在左邊且mid本身已經(jīng)檢查過不是目標(biāo)所以新的右邊界是mid - 1。循環(huán)結(jié)束當(dāng)left right時(shí)搜索區(qū)間為空說明目標(biāo)不存在。第二種左閉右開區(qū)間[left, right)定義left指向可能包含答案的索引right指向的是不包含在搜索空間內(nèi)的第一個(gè)索引類似于迭代器的end()。初始化left 0,right nums.length。注意right初始值等于數(shù)組長(zhǎng)度因?yàn)樗赶虻氖恰拔埠蟆蔽恢?。循環(huán)條件while (left right)。當(dāng)left right時(shí)區(qū)間[left, right)已經(jīng)為空沒有元素需要檢查。邊界更新如果nums[mid] target目標(biāo)在右邊mid已檢查非目標(biāo)新左邊界left mid 1。如果nums[mid] target目標(biāo)在左邊但注意right是開區(qū)間它指向的是不包含的位置。mid已經(jīng)比目標(biāo)大所以新的右邊界應(yīng)該把mid排除在外即right mid。循環(huán)結(jié)束當(dāng)left right時(shí)搜索區(qū)間為空。實(shí)操心得我強(qiáng)烈建議初學(xué)者甚至是有經(jīng)驗(yàn)的開發(fā)者在解決新問題時(shí)優(yōu)先使用左閉右開區(qū)間[left, right)。原因有三第一它的邊界更新邏輯更統(tǒng)一left mid 1和right mid不容易出錯(cuò)第二它處理“尋找邊界”類問題如第一個(gè)大于等于target的位置時(shí)更加自然第三它的結(jié)束條件left right直接指向一個(gè)非常有意義的位置通常是插入位置或邊界便于后續(xù)處理。在后續(xù)的“萬(wàn)能模板”中我們也將基于此區(qū)間定義。3.2 循環(huán)不變量你的算法“信仰”循環(huán)不變量是指在循環(huán)開始前、每次迭代后都保持不變的條件。對(duì)于二分查找我們的循環(huán)不變量就是目標(biāo)值如果存在一定在當(dāng)前定義的搜索區(qū)間內(nèi)。在[left, right)區(qū)間定義下這個(gè)不變量就是在每一輪循環(huán)開始時(shí)目標(biāo)值target如果存在于數(shù)組中那么它的索引i一定滿足left i right。我們所有的邊界更新操作都必須維護(hù)這個(gè)不變量。當(dāng)nums[mid] target時(shí)我們知道target不可能在[left, mid]區(qū)間因?yàn)閿?shù)組有序所以將left更新為mid 1新的區(qū)間[mid1, right)依然包含target如果存在。當(dāng)nums[mid] target時(shí)注意這里用了這是尋找左邊界的關(guān)鍵我們知道target可能在[left, mid]區(qū)間但mid本身可能是目標(biāo)也可能是第一個(gè)大于目標(biāo)的值。為了保持區(qū)間左閉右開我們將right更新為mid新區(qū)間[left, mid)依然可能包含target如果target存在且mid是第一個(gè)等于target的位置那么target的實(shí)際索引就是mid但我們的區(qū)間是[left, mid)不包含mid這會(huì)不會(huì)矛盾不這恰恰是我們尋找“左邊界”的意圖我們讓區(qū)間不斷向左收縮直到鎖定邊界。最終left會(huì)指向那個(gè)邊界。想明白了搜索區(qū)間和循環(huán)不變量代碼怎么寫就變成了一個(gè)按部就班的填空題。下面我們就來揭曉那個(gè)“萬(wàn)能模板”。4. 二分查找萬(wàn)能模板解析與實(shí)現(xiàn)這個(gè)模板的核心是處理三種最常見的二分查找場(chǎng)景1查找精確值2查找左邊界第一個(gè)大于等于target的值3查找右邊界最后一個(gè)小于等于target的值。我們將用一個(gè)統(tǒng)一的框架來應(yīng)對(duì)。4.1 模板代碼與注釋/** * 二分查找萬(wàn)能模板 * param nums 有序數(shù)組假設(shè)為非遞減 * param target 目標(biāo)值 * return 根據(jù)場(chǎng)景不同返回索引值。未找到時(shí)返回-1或插入位置。 */ public int binarySearch(int[] nums, int target) { // 防御性編程 if (nums null || nums.length 0) { return -1; // 或根據(jù)場(chǎng)景返回0 } int left 0; int right nums.length; // 注意使用左閉右開區(qū)間 [left, right) // 循環(huán)不變量目標(biāo)值若存在其索引i一定滿足 left i right while (left right) { // 防止溢出 int mid left (right - left) / 2; // ********** 核心決策邏輯 ********** // // 場(chǎng)景1查找精確值 (標(biāo)準(zhǔn)二分查找) // if (nums[mid] target) { // return mid; // } else if (nums[mid] target) { // left mid 1; // } else { // right mid; // } // 場(chǎng)景2查找左邊界 (第一個(gè) target 的元素) if (nums[mid] target) { right mid; // 目標(biāo)在左半部分包括mid本身因?yàn)閙id可能就是要找的左邊界 } else { left mid 1; // 目標(biāo)在右半部分 } // 場(chǎng)景3查找右邊界 (最后一個(gè) target 的元素) // 通常轉(zhuǎn)化為“查找第一個(gè) target 的元素”然后將其索引減1 // if (nums[mid] target) { // left mid 1; // 目標(biāo)在右半部分包括mid // } else { // right mid; // } // 循環(huán)結(jié)束后left是第一個(gè)target的位置left-1就是最后一個(gè)target的位置 } // 循環(huán)結(jié)束left right // 對(duì)于查找左邊界場(chǎng)景2 // left 指向第一個(gè) target 的位置。 // 需要檢查 left 是否越界以及 nums[left] 是否等于 target。 if (left nums.length || nums[left] ! target) { return -1; // 未找到目標(biāo)值 } return left; // 對(duì)于查找精確值場(chǎng)景1在循環(huán)內(nèi)已返回。 // 對(duì)于查找右邊界場(chǎng)景3返回 left - 1并同樣需要檢查有效性。 }4.2 模板逐行解讀與設(shè)計(jì)邏輯初始化 (right nums.length)我們堅(jiān)持使用左閉右開區(qū)間[left, right)。right初始化為數(shù)組長(zhǎng)度意味著整個(gè)數(shù)組都在初始搜索空間內(nèi)。循環(huán)條件 (while (left right))只要區(qū)間不為空l(shuí)eft right就繼續(xù)搜索。當(dāng)left right時(shí)區(qū)間變?yōu)閇left, left)這是一個(gè)空區(qū)間循環(huán)結(jié)束。中間值計(jì)算 (mid left (right - left) / 2)這是防止整數(shù)溢出的標(biāo)準(zhǔn)寫法。在Java、C等語(yǔ)言中(left right) / 2在兩者之和超過Integer.MAX_VALUE時(shí)會(huì)溢出變成負(fù)數(shù)導(dǎo)致計(jì)算錯(cuò)誤。left (right - left) / 2在數(shù)學(xué)上等價(jià)但避免了加法溢出。核心決策邏輯這是模板的靈魂需要根據(jù)具體場(chǎng)景調(diào)整if判斷條件。查找左邊界 (第一個(gè) target)使用if (nums[mid] target)。為什么是因?yàn)槲覀兊哪繕?biāo)是找到第一個(gè)大于或等于target的位置。當(dāng)nums[mid]等于target時(shí)它可能就是我們要找的左邊界但我們不能直接返回因?yàn)樽筮吙赡苓€有更早的等于target的元素。所以我們將right設(shè)為mid在左側(cè)區(qū)間[left, mid)中繼續(xù)尋找。這個(gè)操作保證了right的左邊包括right指向的位置始終滿足 target。最終當(dāng)區(qū)間收縮到一點(diǎn)時(shí)left就指向了第一個(gè)滿足 target的位置。查找精確值在循環(huán)內(nèi)判斷相等并返回。這是最基礎(chǔ)的變體。查找右邊界模板中注釋了另一種邏輯。通常尋找最后一個(gè) target的元素可以轉(zhuǎn)化為尋找第一個(gè) target的元素然后將其索引減1。代碼中當(dāng)nums[mid] target時(shí)說明目標(biāo)在右邊包括mid所以left mid 1。循環(huán)結(jié)束后left指向第一個(gè) target的位置那么left - 1就是最后一個(gè) target的位置。邊界更新這是維護(hù)循環(huán)不變量的關(guān)鍵步驟。當(dāng)條件滿足如nums[mid] target我們將right更新為mid。因?yàn)閙id可能已經(jīng)是或超過了目標(biāo)邊界新的搜索區(qū)間[left, mid)仍然可能包含我們要找的邊界。當(dāng)條件不滿足如nums[mid] target我們將left更新為mid 1。因?yàn)閙id已經(jīng)明確小于目標(biāo)它絕不可能是我們要找的位置所以從mid1開始搜索。后處理循環(huán)結(jié)束后left和right相等。這個(gè)位置的意義取決于你的決策邏輯。對(duì)于查找左邊界left是第一個(gè) target的索引。你需要檢查①left是否等于數(shù)組長(zhǎng)度意味著所有元素都小于target②nums[left]是否等于target如果只想找等于target的左邊界。根據(jù)檢查結(jié)果返回left或-1。對(duì)于查找右邊界left是第一個(gè) target的索引那么left - 1就是最后一個(gè) target的索引。同樣需要檢查left - 1是否越界left 0以及值是否匹配。注意事項(xiàng)這個(gè)模板的美妙之處在于你只需要修改核心決策邏輯中的比較條件nums[mid]和target的關(guān)系以及最后的返回值處理就能適應(yīng)絕大多數(shù)二分查找問題。再也不用為left、right怎么變而頭疼了。5. 實(shí)戰(zhàn)演練用模板解決三類經(jīng)典問題理論說得再多不如代碼跑一遍。我們直接用上面的模板來解決LeetCode上最經(jīng)典的三個(gè)二分查找問題。我會(huì)展示如何將模板“套用”進(jìn)去并解釋每一步的思考過程。5.1 案例一基礎(chǔ)查找LeetCode 704題目給定一個(gè)n個(gè)元素有序的升序整型數(shù)組nums和一個(gè)目標(biāo)值target寫一個(gè)函數(shù)搜索nums中的target如果目標(biāo)值存在返回下標(biāo)否則返回-1。分析這是最標(biāo)準(zhǔn)的二分查找查找精確值。我們可以在循環(huán)內(nèi)部判斷相等并直接返回。模板應(yīng)用class Solution { public int search(int[] nums, int target) { if (nums null || nums.length 0) return -1; int left 0, right nums.length; // [left, right) while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; // 找到直接返回 } else if (nums[mid] target) { left mid 1; // 目標(biāo)在右側(cè) } else { right mid; // 目標(biāo)在左側(cè) } } // 循環(huán)結(jié)束未找到 return -1; } }要點(diǎn)在找到精確匹配時(shí)立即返回這是與尋找邊界問題的主要區(qū)別。循環(huán)內(nèi)的else分支對(duì)應(yīng)nums[mid] target此時(shí)更新right mid。5.2 案例二尋找左邊界LeetCode 34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置 - 找起始位置題目找出給定目標(biāo)值在數(shù)組中的開始位置。如果不存在返回-1。分析這等價(jià)于尋找第一個(gè) target的元素位置并且需要驗(yàn)證該位置的值是否等于target。模板應(yīng)用class Solution { public int[] searchRange(int[] nums, int target) { int start findLeftBound(nums, target); if (start -1) return new int[]{-1, -1}; int end findRightBound(nums, target); return new int[]{start, end}; } private int findLeftBound(int[] nums, int target) { if (nums null || nums.length 0) return -1; int left 0, right nums.length; // [left, right) while (left right) { int mid left (right - left) / 2; // 核心尋找第一個(gè) target 的位置 if (nums[mid] target) { right mid; } else { left mid 1; } } // 循環(huán)結(jié)束left是第一個(gè)target的位置 // 檢查1.是否越界 2.值是否等于target if (left nums.length || nums[left] ! target) { return -1; } return left; } private int findRightBound(int[] nums, int target) { if (nums null || nums.length 0) return -1; int left 0, right nums.length; // [left, right) while (left right) { int mid left (right - left) / 2; // 核心尋找第一個(gè) target 的位置 if (nums[mid] target) { right mid; } else { left mid 1; } } // 循環(huán)結(jié)束left是第一個(gè)target的位置 // 那么 left - 1 就是最后一個(gè) target 的位置 // 檢查1. left-1是否越界 2. 值是否等于target if (left - 1 0 || nums[left - 1] ! target) { return -1; } return left - 1; } }要點(diǎn)findLeftBound函數(shù)完全使用了模板中的“場(chǎng)景2”邏輯。后處理時(shí)left可能是數(shù)組長(zhǎng)度所有數(shù)都小于target也可能指向一個(gè)不等于target的數(shù)需要檢查。findRightBound函數(shù)使用了“尋找第一個(gè)大于target的位置”的策略。注意if條件變成了nums[mid] target。循環(huán)結(jié)束后left - 1就是我們要的右邊界。同樣需要檢查有效性。5.3 案例三尋找峰值元素LeetCode 162題目峰值元素是指其值嚴(yán)格大于左右相鄰值的元素。給你一個(gè)整數(shù)數(shù)組nums找到峰值元素并返回其索引。數(shù)組可能包含多個(gè)峰值返回任何一個(gè)即可。你可以假設(shè)nums[-1] nums[n] -∞。分析數(shù)組無序但根據(jù)題意和邊界條件我們可以利用局部單調(diào)性進(jìn)行二分。核心是比較nums[mid]和nums[mid1]如果nums[mid] nums[mid1]說明處于上升坡峰值一定在mid右側(cè)包括mid1所以left mid 1。如果nums[mid] nums[mid1]說明mid本身可能是一個(gè)峰值或者處于下降坡峰值在mid左側(cè)包括mid所以right mid。 這依然符合我們“縮小搜索區(qū)間”的二分思想。模板應(yīng)用class Solution { public int findPeakElement(int[] nums) { if (nums null || nums.length 0) return -1; int left 0, right nums.length - 1; // 注意這里用閉區(qū)間更方便處理mid1 while (left right) { // 循環(huán)直到 left right int mid left (right - left) / 2; if (nums[mid] nums[mid 1]) { // 上坡峰值在右側(cè) left mid 1; } else { // 下坡或峰頂峰值在左側(cè)包含mid right mid; } } // 當(dāng) left right 時(shí)即為我們找到的一個(gè)峰值索引 return left; } }要點(diǎn)這個(gè)問題展示了二分查找不局限于“有序數(shù)組”只要存在某種單調(diào)性這里是局部單調(diào)性沿著某個(gè)方向走一定能找到峰值就可以使用二分來快速逼近答案。我們調(diào)整了比較對(duì)象nums[mid]和nums[mid1]但邊界更新的邏輯內(nèi)核與模板一致。6. 避坑指南與高頻問題排查即使有了模板在實(shí)際編碼和調(diào)試中還是會(huì)遇到一些典型問題。下面是我總結(jié)的“踩坑實(shí)錄”和解決方案。6.1 問題一死循環(huán)現(xiàn)象程序在某個(gè)測(cè)試用例上永遠(yuǎn)運(yùn)行不結(jié)束。根因邊界更新不當(dāng)導(dǎo)致搜索區(qū)間無法繼續(xù)縮小。最常見于while (left right)且更新語(yǔ)句為left mid的情況。案例在[left, right)區(qū)間left 0, right 1計(jì)算mid 0。如果分支判斷讓left mid則left仍為0區(qū)間不變陷入死循環(huán)。解決牢記模板的更新規(guī)則在[left, right)下left的更新一定是mid 1right的更新一定是mid。這能保證區(qū)間每次迭代至少縮小1。6.2 問題二返回結(jié)果錯(cuò)誤或漏掉元素現(xiàn)象對(duì)于某些邊界情況如目標(biāo)值在數(shù)組開頭、結(jié)尾或不存在時(shí)返回的索引錯(cuò)誤。根因后處理邏輯不完整或循環(huán)條件選擇錯(cuò)誤。排查清單檢查初始區(qū)間確認(rèn)right的初始化是nums.length左閉右開還是nums.length - 1閉區(qū)間必須與循環(huán)條件匹配。檢查循環(huán)結(jié)束后的狀態(tài)畫出區(qū)間收縮的最終狀態(tài)。對(duì)于左邊界查找循環(huán)結(jié)束后left指向第一個(gè) target的位置。你需要思考如果所有元素都小于targetleft會(huì)等于nums.length。你的代碼處理了嗎如果left在數(shù)組范圍內(nèi)但nums[left] ! target說明target不存在。你的代碼返回-1了嗎單步調(diào)試用最少的元素如空數(shù)組、單元素?cái)?shù)組、兩個(gè)元素?cái)?shù)組和邊界值目標(biāo)值小于最小值、等于某個(gè)值、大于最大值作為測(cè)試用例在腦中或紙上模擬代碼運(yùn)行。6.3 問題三如何選擇while (left right)還是while (left right)這是一個(gè)哲學(xué)問題但模板給出了明確答案統(tǒng)一使用while (left right)和左閉右開區(qū)間[left, right)。一致性所有二分問題找精確值、找左邊界、找右邊界都可以用這套框架解決只需修改核心判斷條件和后處理。簡(jiǎn)潔性循環(huán)結(jié)束條件left right指向的位置通常就是答案或答案的相鄰位置語(yǔ)義清晰。減少錯(cuò)誤避免了在while (left right)循環(huán)結(jié)束后還需要糾結(jié)left和right哪個(gè)是答案的麻煩。當(dāng)然如果你對(duì)閉區(qū)間[left, right]非常熟悉并且能保證不出錯(cuò)繼續(xù)使用也可以。但從教學(xué)和統(tǒng)一心智模型的角度我強(qiáng)烈推薦左閉右開區(qū)間。6.4 一份自檢清單在寫完二分查找代碼后問自己以下幾個(gè)問題數(shù)組為空或?yàn)閚ull時(shí)我的代碼能處理嗎目標(biāo)值比所有元素都小或都大時(shí)返回值正確嗎目標(biāo)值不存在但數(shù)組中有其他值時(shí)返回值是-1嗎數(shù)組中有重復(fù)的目標(biāo)值時(shí)我是在找第一個(gè)還是最后一個(gè)還是任意一個(gè)我的mid計(jì)算方式防止溢出嗎我的循環(huán)在left和right相鄰時(shí)能正常退出嗎把這幾個(gè)問題過一遍能幫你排除90%的二分查找Bug。7. 模板的變通與高階應(yīng)用場(chǎng)景萬(wàn)能模板不是死板的教條理解其原理后你可以靈活變通解決更復(fù)雜的問題。7.1 在非整數(shù)域上的二分二分答案二分查找的思想可以應(yīng)用于任何具有單調(diào)性的函數(shù)尋找滿足某個(gè)條件的邊界值。典型問題是“二分答案”。例如LeetCode 410 “分割數(shù)組的最大值”LeetCode 875 “愛吃香蕉的珂珂”。核心思路確定搜索范圍[left, right]這個(gè)范圍是答案可能的最小值和最大值。定義一個(gè)判定函數(shù)check(mid)判斷當(dāng)答案是mid時(shí)是否滿足題目要求。這個(gè)函數(shù)需要基于題目邏輯實(shí)現(xiàn)并且具有單調(diào)性如果mid滿足那么所有大于或小于mid的值也可能滿足。在while (left right)循環(huán)中計(jì)算mid根據(jù)check(mid)的結(jié)果按照模板更新left或right。循環(huán)結(jié)束后的left或right就是所求的答案。示例框架// 假設(shè)我們要找滿足條件的最小值 int left minPossibleAnswer; // 答案下界 int right maxPossibleAnswer; // 答案上界 while (left right) { int mid left (right - left) / 2; if (check(mid)) { // mid 滿足條件說明答案可能 mid向左搜索包含mid right mid; } else { // mid 不滿足條件說明答案必須 mid向右搜索 left mid 1; } } // 循環(huán)結(jié)束left 是滿足條件的最小值 return left;7.2 在復(fù)雜數(shù)據(jù)結(jié)構(gòu)上的應(yīng)用二分查找的關(guān)鍵是“隨機(jī)訪問”中間元素。因此只要數(shù)據(jù)結(jié)構(gòu)支持O(1)時(shí)間的索引訪問就可以應(yīng)用。例如數(shù)組最直接的應(yīng)用。內(nèi)存中的連續(xù)數(shù)據(jù)結(jié)構(gòu)如ArrayList。通過索引映射的虛擬數(shù)組例如在一個(gè)已知最大值和單調(diào)性的數(shù)學(xué)函數(shù)上尋找解。對(duì)于鏈表等不支持隨機(jī)訪問的數(shù)據(jù)結(jié)構(gòu)二分查找的O(log n)優(yōu)勢(shì)就不復(fù)存在了因?yàn)樵L問中間節(jié)點(diǎn)需要O(n)時(shí)間。7.3 與其它算法結(jié)合二分查找常作為子過程嵌入更復(fù)雜的算法中快速選擇算法在快速排序的 partition 過程中通過比較 pivot 的索引與目標(biāo)索引決定對(duì)哪邊進(jìn)行遞歸類似于二分。二叉搜索樹BST的查找過程本身就是二分思想在樹形結(jié)構(gòu)上的體現(xiàn)。數(shù)據(jù)庫(kù)索引B樹索引的層間查找本質(zhì)上也是多路二分。掌握二分查找的模板不僅僅是學(xué)會(huì)了一個(gè)算法更是掌握了一種高效縮小問題規(guī)模的思維方式。這種思維是優(yōu)化算法、降低時(shí)間復(fù)雜度的利器。我個(gè)人的體會(huì)是初期死記硬背這個(gè)模板在各類題目中反復(fù)套用、調(diào)試、理解。當(dāng)熟練到一定程度后你就不再需要“背”了因?yàn)槟銓?duì)搜索區(qū)間和循環(huán)不變量的理解已經(jīng)深入骨髓可以針對(duì)任何變種問題迅速推導(dǎo)出正確的代碼。這大概就是所謂“無招勝有招”的境界吧。最后一個(gè)小技巧在面試中如果你被問到二分查找可以先和面試官明確你使用的區(qū)間定義“我習(xí)慣使用左閉右開區(qū)間”然后基于此展開書寫和解釋這會(huì)讓你的思路顯得非常清晰和專業(yè)。