企业官网建设流程全解析

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

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

二分查找（Binary Search）是排序数组上最经典的高效查找算法，能够在 $O(\log n)$ 时间内将查找范围每次减半，是算法面试与工程实践中的必备基础。本文以 LeetCode 704（Binary 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）为止。

算法步骤

1. 定义一个接收当前搜索区间[l, r]的递归函数；
2. 若l > r，区间为空，返回-1；
3. 计算中间下标m = (l + r) // 2；
4. 比较nums[m]与target：
   • 相等 → 返回m；
   • nums[m] < target→ 递归搜索[m + 1, r]；
   • nums[m] > target→ 递归搜索[l, m - 1]；
5. 以完整区间[0, n - 1]启动递归；
6. 返回最终结果。

多语言实现

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, vector<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)); } int search(vector<int>& 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(m+1, 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: Vec<i32>, 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）说明目标不存在。

算法步骤

1. 初始化两个指针：
   • l = 0（数组起点）；
   • r = len(nums) - 1（数组终点）。
2. 当l <= r时循环：
   • 计算m = l + (r - l) // 2（安全中点，避免溢出）；
   • 若nums[m] == target，返回m；
   • 若nums[m] < target，搜索右半部分：l = m + 1；
   • 若nums[m] > target，搜索左半部分：r = m - 1。
3. 循环结束仍未找到，返回-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 -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; } }

class Solution { public: int search(vector<int>& 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: Vec<i32>, 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 -> 4；
• c/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。

算法步骤

1. 令l = 0，r = len(nums)（右边界为最后一个下标的下一个位置，即半开区间[l, r)）；
2. 当l < r时循环：
   • 计算中点m；
   • 若nums[m] > target，收缩右侧：r = m；
   • 否则（nums[m] <= target），收缩左侧：l = m + 1；
3. 循环结束后：
   • l即上界：第一个满足nums[l] > target的下标；
   • 因此 target 可能出现的位置是l - 1；
4. 若l > 0且nums[l - 1] == target，返回l - 1；
5. 否则返回-1（target 不存在）。

多语言实现

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 -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; } }

class Solution { public: int search(vector<int>& 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: Vec<i32>, 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 可能出现的最左位置"，再做一次相等验证。

该做法对有序数组尤其有用：它天然避免越过目标，并且自然处理重复元素——返回的永远是第一个命中位置。

算法步骤

1. 初始化：
   • l = 0；
   • r = len(nums)（右边界为最后一个下标的下一个位置，半开区间）。
2. 当l < r时循环：
   • 计算中点m；
   • 若nums[m] >= target，收缩到左半部分：r = m；
   • 否则（nums[m] < target），搜索右半部分：l = m + 1。
3. 循环结束后：
   • l即下界：第一个满足值>= target的下标。
4. 若l在数组范围内且nums[l] == target，返回l；
5. 否则返回-1（target 不在数组中）。

多语言实现

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 -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; } }

class Solution { public: int search(vector<int>& 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: Vec<i32>, 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)$

与上界变体的对比

值得一提的印证是，本仓库 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 -1

public 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(vector<int>& 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: Vec<i32>, target: i32) -> i32 { match nums.binary_search(&target) { Ok(index) => index as i32, Err(_) => -1, } } }

各语言内置函数的关键行为差异：

• Pythonbisect.bisect_left：返回第一个>= target的下标（下界语义），因此要手动验证nums[index] == target；
• JavaArrays.binarySearch：命中返回正下标，未命中返回负数插入点（-(insertion point) - 1），所以用index >= 0判断；
• C++lower_bound：返回迭代器，需同时判断it != nums.end()且*it == target；
• JavaScript：标准库没有二分查找函数，示例使用indexOf（线性扫描），仅作兜底写法；
• C#Array.BinarySearch：与 Java 语义一致，未命中返回负数；
• Gosort.Search：接受一个返回bool的谓词，nums[i] >= target即下界语义，需再做相等验证；
• KotlinIntArray.binarySearch：命中返回下标，未命中返回负数；
• SwiftpartitioningIndex：返回第一个使谓词为真的下标（下界语义），需验证；
• Rustbinary_search：返回Result<usize, usize>，Ok为命中下标，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-one

while l <= r与while l < r行为差异显著：

• l <= r搭配闭区间[l, r]，更新必须l = m + 1/r = m - 1；
• l < 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) // 2规避整数溢出；
• 模板自洽：循环条件与指针更新必须配套，l <= r配l = m + 1/r = m - 1，l < 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