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