二分查找（Binary Search）全解：递归、迭代、上界与下界边界搜索的完整实现指南

二分查找Binary Search全解递归、迭代、上界与下界边界搜索的完整实现指南【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode二分查找Binary Search是排序数组上最经典的高效查找算法能够在 $O(\log n)$ 时间内将查找范围每次减半是算法面试与工程实践中的必备基础。本文以 LeetCode 704Binary Search为原型完整讲解递归版、迭代版、上界Upper Bound、下界Lower Bound以及语言内置函数五种实现思路并结合本仓库leetcode中 12 种语言的真实源码如 python/0704-binary-search.py、cpp/0704-binary-search.cpp、rust/0704-binary-search.rs逐行印证实现细节。读完本文你将掌握二分查找的两种区间模板、两种边界搜索变体以及如何规避整数溢出、死循环、off-by-one 等高频陷阱。前置知识动手之前需要掌握的四个基础原文档在进入正题前强调尝试解决本问题前应当具备以下基础数组Arrays理解数组如何按下标索引与访问。二分查找的所有指针操作都建立在数组的随机访问能力之上nums[m]的 $O(1)$ 访问是算法高效的前提。有序数组Sorted Arrays识别有序数据的特性——单调性让中间元素与目标比较后必然可以舍弃一半这一推理成立。若数组无序二分查找的前提条件即被破坏。递归Recursion能够编写并理解带 base case 的递归函数。递归版二分查找把不断缩小范围表达为函数对自身在某一半上的调用。时间复杂度Time Complexity理解 $O(\log n)$ 与 $O(n)$ 的区别以及为什么每次将搜索空间减半能带来对数级别的效率提升。本仓库的 hints/binary-search.md 对本题的目标复杂度给出了明确提示应以$O(\log n)$ 时间和 $O(1)$ 空间为目标其中 $n$ 是输入数组大小并提示利用数组有序的性质每一步消除一半搜索段。问题原型LeetCode 704 与本仓库的对应实现本文讲解的算法对应 LeetCode 704 号问题给定一个升序排列的整数数组nums与目标值target返回目标值在数组中的下标若不存在则返回-1。本仓库在 README.md 的完成度表格中收录了该题并以多语言实现了完整的解法迭代版主实现c/0704-binary-search.c、cpp/0704-binary-search.cpp、python/0704-binary-search.py、go/0704-binary-search.go、rust/0704-binary-search.rs、swift/0704-binary-search.swift、dart/0704-binary-search.dart、java/0704-binary-search.java、javascript/0704-binary-search.js、kotlin/0704-binary-search.kt、ruby/0704-binary-search.rb、scala/0704-binary-search.scala、typescript/0704-binary-search.ts、csharp/0704-binary-search.cs下文将沿着原文档的五个章节逐一展开每种实现的直觉、算法步骤与多语言代码并在关键处用仓库源码进行印证。一、递归版二分查找直觉Intuition二分查找的核心是反复将搜索空间减半。与其扫描整个数组不如每次检查中间元素若中间元素就是目标 → 直接返回其下标若目标更大 → 只在右半部分继续搜索若目标更小 → 只在左半部分继续搜索。递归版只是把这个思想表达为一个不断在合适的半边调用自身的函数直到找到目标或搜索区间变为非法l r为止。算法步骤定义一个接收当前搜索区间[l, r]的递归函数若l r区间为空返回-1计算中间下标m (l r) // 2比较nums[m]与target相等 → 返回mnums[m] target→ 递归搜索[m 1, r]nums[m] target→ 递归搜索[l, m - 1]以完整区间[0, n - 1]启动递归返回最终结果。多语言实现class Solution: def binary_search(self, l: int, r: int, nums: List[int], target: int) - int: if l r: return -1 m l (r - l) // 2 if nums[m] target: return m if nums[m] target: return self.binary_search(m 1, r, nums, target) return self.binary_search(l, m - 1, nums, target) def search(self, nums: List[int], target: int) - int: return self.binary_search(0, len(nums) - 1, nums, target)public class Solution { public int binary_search(int l, int r, int[] nums, int target) { if (l r) return -1; int m l (r - l) / 2; if (nums[m] target) return m; return (nums[m] target) ? binary_search(m 1, r, nums, target) : binary_search(l, m - 1, nums, target); } public int search(int[] nums, int target) { return binary_search(0, nums.length - 1, nums, target); } }class Solution { public: int binary_search(int l, int r, vectorint nums, int target){ if (l r) return -1; int m l (r - l) / 2; if (nums[m] target) return m; return ((nums[m] target) ? binary_search(m 1, r, nums, target) : binary_search(l, m - 1, nums, target)); } int search(vectorint nums, int target) { return binary_search(0, nums.size() - 1, nums, target); } };class Solution { /** * param {number[]} nums * param {number} target * return {number} */ binary_search(l, r, nums, target) { if (l r) return -1; let m l Math.floor((r - l) / 2); if (nums[m] target) return m; return nums[m] target ? this.binary_search(m 1, r, nums, target) : this.binary_search(l, m - 1, nums, target); } search(nums, target) { return this.binary_search(0, nums.length - 1, nums, target); } }public class Solution { public int BinarySearch(int l, int r, int[] nums, int target) { if (l r) return -1; int m l (r - l) / 2; if (nums[m] target) return m; return (nums[m] target) ? BinarySearch(m 1, r, nums, target) : BinarySearch(l, m - 1, nums, target); } public int Search(int[] nums, int target) { return BinarySearch(0, nums.Length - 1, nums, target); } }func binarySearch(l, r int, nums []int, target int) int { if l r { return -1 } m : l (r-l)/2 if nums[m] target { return m } if nums[m] target { return binarySearch(m1, r, nums, target) } return binarySearch(l, m-1, nums, target) } func search(nums []int, target int) int { return binarySearch(0, len(nums)-1, nums, target) }class Solution { private fun binarySearch(l: Int, r: Int, nums: IntArray, target: Int): Int { if (l r) { return -1 } val m l (r - l) / 2 return when { nums[m] target - m nums[m] target - binarySearch(m 1, r, nums, target) else - binarySearch(l, m - 1, nums, target) } } fun search(nums: IntArray, target: Int): Int { return binarySearch(0, nums.size - 1, nums, target) } }class Solution { func binarySearch(_ l: Int, _ r: Int, _ nums: [Int], _ target: Int) - Int { if l r { return -1 } let m l (r - l) / 2 if nums[m] target { return m } if nums[m] target { return binarySearch(m 1, r, nums, target) } return binarySearch(l, m - 1, nums, target) } func search(_ nums: [Int], _ target: Int) - Int { return binarySearch(0, nums.count - 1, nums, target) } }impl Solution { pub fn search(nums: Veci32, target: i32) - i32 { Self::binary_search(0, nums.len() as i32 - 1, nums, target) } fn binary_search(l: i32, r: i32, nums: [i32], target: i32) - i32 { if l r { return -1; } let m l (r - l) / 2; if nums[m as usize] target { return m; } if nums[m as usize] target { Self::binary_search(m 1, r, nums, target) } else { Self::binary_search(l, m - 1, nums, target) } } }复杂度分析时间复杂度$O(\log n)$。每次递归都把区间缩小一半递归深度为 $\log_2 n$。空间复杂度$O(\log n)$。递归调用栈深度与递归次数成正比若用尾递归优化的语言如部分函数式后端可能降为 $O(1)$但一般语言下仍按 $O(\log n)$ 计算。二、迭代版二分查找直觉Intuition迭代版检查有序数组的中间元素并决定舍弃哪一半。与递归不同迭代版用循环持续收缩搜索区间不断调整左右指针直到找到目标或指针交错l r说明目标不存在。算法步骤初始化两个指针l 0数组起点r len(nums) - 1数组终点。当l r时循环计算m l (r - l) // 2安全中点避免溢出若nums[m] target返回m若nums[m] target搜索右半部分l m 1若nums[m] target搜索左半部分r m - 1。循环结束仍未找到返回-1。多语言实现class Solution: def search(self, nums: List[int], target: int) - int: l, r 0, len(nums) - 1 while l r: # (l r) // 2 can lead to overflow m l ((r - l) // 2) if nums[m] target: r m - 1 elif nums[m] target: l m 1 else: return m return -1public class Solution { public int search(int[] nums, int target) { int l 0, r nums.length - 1; while (l r) { int m l ((r - l) / 2); if (nums[m] target) { r m - 1; } else if (nums[m] target) { l m 1; } else { return m; } } return -1; } }class Solution { public: int search(vectorint nums, int target) { int l 0, r nums.size() - 1; while (l r) { int m l ((r - l) / 2); if (nums[m] target) { r m - 1; } else if (nums[m] target) { l m 1; } else { return m; } } return -1; } };class Solution { /** * param {number[]} nums * param {number} target * return {number} */ search(nums, target) { let l 0; let r nums.length - 1; while (l r) { const m l Math.floor((r - l) / 2); if (nums[m] target) { r m - 1; } else if (nums[m] target) { l m 1; } else { return m; } } return -1; } }public class Solution { public int Search(int[] nums, int target) { int l 0, r nums.Length - 1; while (l r) { int m l ((r - l) / 2); if (nums[m] target) { r m - 1; } else if (nums[m] target) { l m 1; } else { return m; } } return -1; } }func search(nums []int, target int) int { l, r : 0, len(nums)-1 for l r { m : l (r-l)/2 if nums[m] target { r m - 1 } else if nums[m] target { l m 1 } else { return m } } return -1 }class Solution { fun search(nums: IntArray, target: Int): Int { var l 0 var r nums.size - 1 while (l r) { val m l (r - l) / 2 when { nums[m] target - r m - 1 nums[m] target - l m 1 else - return m } } return -1 } }class Solution { func search(_ nums: [Int], _ target: Int) - Int { var l 0, r nums.count - 1 while l r { // (l r) // 2 can lead to overflow let m l (r - l) / 2 if nums[m] target { r m - 1 } else if nums[m] target { l m 1 } else { return m } } return -1 } }impl Solution { pub fn search(nums: Veci32, target: i32) - i32 { let (mut l, mut r) (0i32, nums.len() as i32 - 1); while l r { let m l (r - l) / 2; if nums[m as usize] target { r m - 1; } else if nums[m as usize] target { l m 1; } else { return m; } } -1 } }复杂度分析时间复杂度$O(\log n)$循环每次将区间减半最多执行 $\log_2 n$ 轮。空间复杂度$O(1)$仅使用几个指针变量无额外递归栈开销。仓库源码印证本仓库的多语言实现正是迭代版 闭区间[l, r]模板的直接落地可逐行对照cpp/0704-binary-search.cpp 使用low/high指针与low (high - low) / 2的安全中点写法并在注释中给出示例nums [-1,0,3,5,9,12], target 9 - 4c/0704-binary-search.c 额外补充了未命中示例target 2 - -1展示了有序数组 → 二分查找的完整判断链python/0704-binary-search.py 的注释# (l r) // 2 can lead to overflow与原文档的陷阱提示完全一致go/0704-binary-search.go 与 dart/0704-binary-search.dart后者使用 Dart 的整数除法~/同样遵循l r闭区间模板。三、上界Upper Bound变体直觉Intuition上界二分查找找到的是第一个大于 target 的元素所在的下标。一旦确定该位置真正的 target若存在必然紧邻其左侧。因此我们不再直接寻找相等而是寻找值从 ≤ target 变为 target的边界然后检查边界前一个元素是否等于 target。算法步骤令l 0r len(nums)右边界为最后一个下标的下一个位置即半开区间[l, r)当l r时循环计算中点m若nums[m] target收缩右侧r m否则nums[m] target收缩左侧l m 1循环结束后l即上界第一个满足nums[l] target的下标因此 target 可能出现的位置是l - 1若l 0且nums[l - 1] target返回l - 1否则返回-1target 不存在。多语言实现class Solution: def search(self, nums: List[int], target: int) - int: l, r 0, len(nums) while l r: m l ((r - l) // 2) if nums[m] target: r m elif nums[m] target: l m 1 return l - 1 if (l and nums[l - 1] target) else -1public class Solution { public int search(int[] nums, int target) { int l 0, r nums.length; while (l r) { int m l ((r - l) / 2); if (nums[m] target) { r m; } else { l m 1; } } return (l 0 nums[l - 1] target) ? l - 1 : -1; } }class Solution { public: int search(vectorint nums, int target) { int l 0, r nums.size(); while (l r) { int m l (r - l) / 2; if (nums[m] target) { r m; } else { l m 1; } } return (l 0 nums[l - 1] target) ? l - 1 : -1; } };class Solution { /** * param {number[]} nums * param {number} target * return {number} */ search(nums, target) { let l 0, r nums.length; while (l r) { let m l Math.floor((r - l) / 2); if (nums[m] target) { r m; } else { l m 1; } } return l 0 nums[l - 1] target ? l - 1 : -1; } }public class Solution { public int Search(int[] nums, int target) { int l 0, r nums.Length; while (l r) { int m l (r - l) / 2; if (nums[m] target) { r m; } else { l m 1; } } return (l 0 nums[l - 1] target) ? l - 1 : -1; } }func search(nums []int, target int) int { l, r : 0, len(nums) for l r { m : l (r-l)/2 if nums[m] target { r m } else { l m 1 } } if l 0 nums[l-1] target { return l - 1 } return -1 }class Solution { fun search(nums: IntArray, target: Int): Int { var l 0 var r nums.size while (l r) { val m l (r - l) / 2 if (nums[m] target) { r m } else { l m 1 } } return if (l 0 nums[l - 1] target) l - 1 else -1 } }class Solution { func search(_ nums: [Int], _ target: Int) - Int { var l 0, r nums.count while l r { let m l (r - l) / 2 if nums[m] target { r m } else { l m 1 } } return (l 0 nums[l - 1] target) ? l - 1 : -1 } }impl Solution { pub fn search(nums: Veci32, target: i32) - i32 { let (mut l, mut r) (0usize, nums.len()); while l r { let m l (r - l) / 2; if nums[m] target { r m; } else { l m 1; } } if l 0 nums[l - 1] target { (l - 1) as i32 } else { -1 } } }复杂度分析时间复杂度$O(\log n)$空间复杂度$O(1)$上界变体的关键区别在于使用半开区间[l, r)、循环条件l r、右侧收缩r m而不减一最终答案是边界l的前一个位置l - 1。四、下界Lower Bound变体直觉Intuition下界二分查找找到的是第一个大于等于 target 的元素下标。这意味着如果 target 存在于数组中下界下标恰好指向它的首次出现位置。因此我们搜索target 可能出现的最左位置再做一次相等验证。该做法对有序数组尤其有用它天然避免越过目标并且自然处理重复元素——返回的永远是第一个命中位置。算法步骤初始化l 0r len(nums)右边界为最后一个下标的下一个位置半开区间。当l r时循环计算中点m若nums[m] target收缩到左半部分r m否则nums[m] target搜索右半部分l m 1。循环结束后l即下界第一个满足值 target的下标。若l在数组范围内且nums[l] target返回l否则返回-1target 不在数组中。多语言实现class Solution: def search(self, nums: List[int], target: int) - int: l, r 0, len(nums) while l r: m l ((r - l) // 2) if nums[m] target: r m elif nums[m] target: l m 1 return l if (l len(nums) and nums[l] target) else -1public class Solution { public int search(int[] nums, int target) { int l 0, r nums.length; while (l r) { int m l (r - l) / 2; if (nums[m] target) { r m; } else { l m 1; } } return (l nums.length nums[l] target) ? l : -1; } }class Solution { public: int search(vectorint nums, int target) { int l 0, r nums.size(); while (l r) { int m l (r - l) / 2; if (nums[m] target) { r m; } else { l m 1; } } return (l nums.size() nums[l] target) ? l : -1; } };class Solution { /** * param {number[]} nums * param {number} target * return {number} */ search(nums, target) { let l 0, r nums.length; while (l r) { let m l Math.floor((r - l) / 2); if (nums[m] target) { r m; } else { l m 1; } } return l nums.length nums[l] target ? l : -1; } }public class Solution { public int Search(int[] nums, int target) { int l 0, r nums.Length; while (l r) { int m l (r - l) / 2; if (nums[m] target) { r m; } else { l m 1; } } return (l nums.Length nums[l] target) ? l : -1; } }func search(nums []int, target int) int { l, r : 0, len(nums) for l r { m : l (r-l)/2 if nums[m] target { r m } else { l m 1 } } if l len(nums) nums[l] target { return l } return -1 }class Solution { fun search(nums: IntArray, target: Int): Int { var l 0 var r nums.size while (l r) { val m l (r - l) / 2 if (nums[m] target) { r m } else { l m 1 } } return if (l nums.size nums[l] target) l else -1 } }class Solution { func search(_ nums: [Int], _ target: Int) - Int { var l 0, r nums.count while l r { let m l (r - l) / 2 if nums[m] target { r m } else { l m 1 } } return (l nums.count nums[l] target) ? l : -1 } }impl Solution { pub fn search(nums: Veci32, target: i32) - i32 { let (mut l, mut r) (0usize, nums.len()); while l r { let m l (r - l) / 2; if nums[m] target { r m; } else { l m 1; } } if l nums.len() nums[l] target { l as i32 } else { -1 } } }复杂度分析时间复杂度$O(\log n)$空间复杂度$O(1)$与上界变体的对比维度上界 Upper Bound下界 Lower Bound搜索目标第一个 target的下标第一个 target的下标收缩条件nums[m] target → r m否则l m 1nums[m] target → r m否则l m 1返回位置l - 1target 若存在则在边界左侧ltarget 若存在则正是下界本身重复元素返回最后一次出现位置返回第一次出现位置复杂度$O(\log n)$ / $O(1)$$O(\log n)$ / $O(1)$值得一提的印证是本仓库 rust/0704-binary-search.rs 虽然也是本题解法但采用了半开区间写法r nums.len()、l r、命中前用Less r m收缩其结构与下界模板一脉相承——说明同一道题可以用不同区间模板实现重要的是保持循环条件与指针更新的自洽。五、语言内置函数实现如果语言标准库提供了二分查找可以直接调用代码最简、最不易出错。各语言的内置函数语义略有差异实现时需注意返回值约定import bisect class Solution: def search(self, nums: List[int], target: int) - int: index bisect.bisect_left(nums, target) return index if index len(nums) and nums[index] target else -1public class Solution { public int search(int[] nums, int target) { int index Arrays.binarySearch(nums, target); return index 0 ? index : -1; } }class Solution { public: int search(vectorint nums, int target) { auto it lower_bound(nums.begin(), nums.end(), target); return (it ! nums.end() *it target) ? it - nums.begin() : -1; } };class Solution { /** * param {number[]} nums * param {number} target * return {number} */ search(nums, target) { // There is no built in function for JS. return nums.indexOf(target); } }public class Solution { public int Search(int[] nums, int target) { int index Array.BinarySearch(nums, target); return index 0 ? index : -1; } }func search(nums []int, target int) int { index : sort.Search(len(nums), func(i int) bool { return nums[i] target }) if index len(nums) nums[index] target { return index } return -1 }class Solution { fun search(nums: IntArray, target: Int): Int { val index nums.binarySearch(target) return if (index 0) index else -1 } }class Solution { func search(_ nums: [Int], _ target: Int) - Int { let index nums.partitioningIndex { $0 target } return (index nums.count nums[index] target) ? index : -1 } }impl Solution { pub fn search(nums: Veci32, target: i32) - i32 { match nums.binary_search(target) { Ok(index) index as i32, Err(_) -1, } } }各语言内置函数的关键行为差异Pythonbisect.bisect_left返回第一个 target的下标下界语义因此要手动验证nums[index] targetJavaArrays.binarySearch命中返回正下标未命中返回负数插入点-(insertion point) - 1所以用index 0判断Clower_bound返回迭代器需同时判断it ! nums.end()且*it targetJavaScript标准库没有二分查找函数示例使用indexOf线性扫描仅作兜底写法C#Array.BinarySearch与 Java 语义一致未命中返回负数Gosort.Search接受一个返回bool的谓词nums[i] target即下界语义需再做相等验证KotlinIntArray.binarySearch命中返回下标未命中返回负数SwiftpartitioningIndex返回第一个使谓词为真的下标下界语义需验证Rustbinary_search返回Resultusize, usizeOk为命中下标Err为插入点。复杂度分析时间复杂度$O(\log n)$注意 JavaScript 示例的indexOf是 $O(n)$仅作演示空间复杂度$O(1)$六、常见陷阱与调试指南原文档专门列出了四类高频错误这也是二分查找面试中被反复考察的细节逐一展开如下1. 计算中点时的整数溢出使用(l r) / 2在l与r都很大例如接近INT_MAX时会溢出。正确写法是l (r - l) / 2先求区间长度再偏移从数学上等价且永远安全# Wrong: can overflow in some languages m (l r) // 2 # Correct: prevents overflow m l (r - l) // 2仓库中的 cpp/0704-binary-search.cpp 与 c/0704-binary-search.c 都采用了low (high - low) / 2的安全写法而 python/0704-binary-search.py 更是直接以注释形式标注了这一风险可见这是社区共识级别的工程细节。2. 指针更新错误导致的死循环将l m写成l m 1或在某些变体中把r m写成r m - 1会在l与r相邻时陷入死循环此时m l若继续l m区间永远无法缩小。凡使用l m的写法都必须保证m是向上取整如m l (r - l 1) // 2这也是求上界/找右侧边界模板的经典易错点。3. 循环条件的 off-by-onewhile l r与while l r行为差异显著l r搭配闭区间[l, r]更新必须l m 1/r m - 1l r搭配半开区间[l, r)更新必须l m 1/r m。混用二者且指针更新不配套是绝大多数二分查找 bug 的根源。建议选定一套模板并全程保持一致即原文档强调的 Be consistent with your chosen template。4. 未验证目标是否真的被找到二分查找最终会收敛到某个位置但该位置未必包含目标。上界/下界变体返回的只是一个边界位置因此在返回前必须验证nums[result] target并检查下标边界否则会把未命中误判为命中。本文第三、四章所有实现都严格遵循了这一验证步骤。七、边界搜索变体的实战延伸掌握了上界/下界这两个二分查找原子操作后可以显著降低一系列进阶题的思考成本。本仓库的 articles 目录收录了大量依赖二分思想或边界搜索的问题可作为延伸练习首个与最后一个位置find-first-and-last-position-of-element-in-sorted-array.md —— 正是下界 上界两次二分查找的直接应用旋转数组find-minimum-in-rotated-sorted-array.md、find-target-in-rotated-sorted-array.md、search-in-rotated-sorted-array-ii.md —— 在部分有序区间上继续使用减半思想二分答案在值域上二分eating-bananas.md、capacity-to-ship-packages-within-d-days.md、kth-largest-element-in-an-array.md、split-array-largest-sum.md —— 把对下标二分推广为对答案取值二分二维与更复杂场景search-2d-matrix.md、find-peak-element.md、time-based-key-value-store.md。这些题目共同验证了一个规律只要数据具备单调性二分查找就可能是候选解法——本文的四套模板与内置函数实现足以覆盖其中绝大多数需求。总结本文围绕 LeetCode 704 二分查找完整覆盖了五种实现实现区间形式循环/递归条件空间复杂度适用场景递归版闭区间[l, r]l r终止$O(\log n)$理解递归思想、函数式写法迭代版闭区间[l, r]l r$O(1)$默认首选无栈开销上界 Upper Bound半开区间[l, r)l r$O(1)$找最后一个命中位置、右侧边界下界 Lower Bound半开区间[l, r)l r$O(1)$找第一个命中位置、处理重复元素内置函数语言标准库语义依库而定$O(1)$生产代码追求简洁可靠关键要点回顾核心前提数组必须有序比较函数需满足单调性安全中点始终使用l (r - l) // 2规避整数溢出模板自洽循环条件与指针更新必须配套l r配l m 1/r m - 1l r配l m 1/r m边界验证上界/下界变体返回位置后务必验证nums[result] target并检查边界多语言落地本仓库提供了 14 种语言的完整实现如 cpp/0704-binary-search.cpp、c/0704-binary-search.c、go/0704-binary-search.go、rust/0704-binary-search.rs可与本文代码逐一对照学习。二分查找虽只有短短十余行但区间模板、边界条件、溢出处理三者缺一不可。吃透本文的五种实现与四类陷阱你便能在面试与工程中游刃有余并顺利迁移到旋转数组、二分答案等更复杂的场景中。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考