京公网安备11010502063487号给定一个升序、元素互不相同的数组和一个目标值：如果目标在数组里就返回它的下标，否则返回它按顺序应该插入的位置。换个说法，就是"第一个大于等于 target 的位置"，都比 target 小就是数组长度。这是二分查找最标准的形态，也是后面所有二分变体的基础：左闭右开区间 [lo, hi)，nums[mid] < target 时丢掉左半，否则丢掉右半。这道题里最值得实测的是一个几十年的老坑：(lo + hi) / 2 在整数溢出时会算出负数。本文用真实的 Java 和 C++ 程序展示它，给出五种语言的实现，并把二分做成分步演示。
完整题目见官方页面（链接在文末）。基准解是"数一数数组里有几个元素比 target 小"，这个个数就是插入位置，与二分完全不同。一共 12 组用例，覆盖：官方示例、目标比所有元素都小、比所有元素都大、单个元素的三种情形、负数：
输入 [[1,3,5,6],5] 输出 2 输入 [[1,3,5,6],2] 输出 1 输入 [[1,3,5,6],7] 输出 4 输入 [[1,3,5,6],0] 输出 0 输入 [[1],0] 输出 0 输入 [[1],1] 输出 0
32 位有符号整数的最大值约 21.47 亿。当数组很长、lo 和 hi 都很大时，lo + hi 可能超过这个范围，回绕成负数，再除以 2 得到的中点是负的，会导致数组越界。下面直接取 lo = 15 亿、hi = 20 亿 做计算（真实的数组要超过 20 亿个元素才会出现这种情形，但两个整数相加的行为是一样的）：
lo = 1500000000，hi = 2000000000（数组长度超过 20 亿时才会真的出现，这里直接对两个整数做计算）： Java: (lo + hi) / 2 = -397483648 Java: lo + (hi - lo) / 2 = 1750000000 C++ (按 int 相加回绕后再除 2): -397483648 C++ lo + (hi - lo) / 2 = 1750000000 Python（整数不会溢出）: (lo + hi) // 2 = 1750000000
Java 的 (lo + hi) / 2 得到 -397483648，一个负数，而 lo + (hi - lo) / 2 得到正确的 1750000000。C++ 里有符号整数溢出是未定义行为，我用无符号加法模拟了回绕的结果，同样得到了 -397483648，再用 lo + (hi - lo) / 2 得到 1750000000。Python 的整数不会溢出，所以没有这个问题。本文所有语言里都把中点写成 lo + (hi - lo) / 2，它在 lo、hi 都是非负整数时不会溢出。
搜索区间是 [lo, hi)，初始 lo = 0、hi = n，答案可能是 n（都比 target 小），所以 hi 取 n 而不是 n - 1。循环条件 lo < hi：取中点，nums[mid] < target 说明 mid 及左边都太小，lo = mid + 1；否则 mid 可能就是答案，hi = mid，注意不是 mid - 1。区间为空时 lo == hi，它就是第一个大于等于 target 的位置。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums, target): lo, hi = 0, len(nums) # 搜索区间是左闭右开 [lo, hi)，答案可能是 len(nums) while lo < hi: mid = lo + (hi - lo) // 2 # 写成 lo + (hi - lo) / 2，避免 lo + hi 溢出 if nums[mid] < target: lo = mid + 1 # mid 太小，答案在它右边 else: hi = mid # mid 满足 >= target，它可能就是答案 return lo
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,3,5,6],5] → 2 [[1,3,5,6],2] → 1 [[1,3,5,6],7] → 4 [[1,3,5,6],0] → 0 [[1],0] → 0 [[1],1] → 0
Java · 解法代码class Solution { public int searchInsert(int[] nums, int target) { int lo = 0, hi = nums.length; // 搜索区间是左闭右开 [lo, hi)，答案可能是 nums.length while (lo < hi) { int mid = lo + (hi - lo) / 2; // 写成 lo + (hi - lo) / 2，避免 lo + hi 溢出 if (nums[mid] < target) lo = mid + 1; // mid 太小，答案在它右边 else hi = mid; // mid 满足 >= target，它可能就是答案 } return lo; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,3,5,6],5] → 2 [[1,3,5,6],2] → 1 [[1,3,5,6],7] → 4 [[1,3,5,6],0] → 0 [[1],0] → 0 [[1],1] → 0
Go · 解法代码func searchInsert(nums []int, target int) int { lo, hi := 0, len(nums) // 搜索区间是左闭右开 [lo, hi)，答案可能是 len(nums) for lo < hi { mid := lo + (hi-lo)/2 // 写成 lo + (hi - lo) / 2，避免 lo + hi 溢出 if nums[mid] < target { lo = mid + 1 // mid 太小，答案在它右边 } else { hi = mid // mid 满足 >= target，它可能就是答案 } } return lo }
$ go build -o bin . && ./bin < cases.jsonl [[1,3,5,6],5] → 2 [[1,3,5,6],2] → 1 [[1,3,5,6],7] → 4 [[1,3,5,6],0] → 0 [[1],0] → 0 [[1],1] → 0
JavaScript · 解法代码function searchInsert(nums, target) { let lo = 0, hi = nums.length; // 搜索区间是左闭右开 [lo, hi)，答案可能是 nums.length while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); // JS 数字是双精度，不会溢出，但保持同样的写法 if (nums[mid] < target) lo = mid + 1; // mid 太小，答案在它右边 else hi = mid; // mid 满足 >= target，它可能就是答案 } return lo; }
$ node run.js < cases.jsonl [[1,3,5,6],5] → 2 [[1,3,5,6],2] → 1 [[1,3,5,6],7] → 4 [[1,3,5,6],0] → 0 [[1],0] → 0 [[1],1] → 0
C++ · 解法代码#include <vector> using namespace std; class Solution { public: int searchInsert(vector<int>& nums, int target) { int lo = 0, hi = nums.size(); // 搜索区间是左闭右开 [lo, hi)，答案可能是 nums.size() while (lo < hi) { int mid = lo + (hi - lo) / 2; // 写成 lo + (hi - lo) / 2，避免 lo + hi 溢出 if (nums[mid] < target) lo = mid + 1; // mid 太小，答案在它右边 else hi = mid; // mid 满足 >= target，它可能就是答案 } return lo; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,3,5,6],5] → 2 [[1,3,5,6],2] → 1 [[1,3,5,6],7] → 4 [[1,3,5,6],0] → 0 [[1],0] → 0 [[1],1] → 0
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
目标取 n（大于数组里的所有元素），这是二分要走完整个区间收缩过程的情形。基准（数一数比 target 小的元素）是线性的，每个规模取三次中最快的一次：
数组长度 n（找 n 这个大于全部元素的值） | 暴力解 | 本文解法
10000 | 0.185 ms | 0.001 ms
100000 | 1.874 ms | 0.001 ms
1000000 | 19.247 ms | 0.005 ms
3000000 | 59.762 ms | 0.011 ms线性做法（这里是一次 C 实现的遍历）随长度线性增长，300 万时约 59.8ms；二分只需约 22 次比较，耗时是微秒量级（300 万时约 0.011ms）。二分在小规模上的读数受计时精度影响，没有细究。
Python 版本另外和"数一数比 target 小的元素"做了随机对拍，包括目标比所有元素都小、都大、夹在中间和正好存在的所有情形：
随机对拍 20000 组（长度 1 到 12、互不相同的升序数组，target 取 -17 到 17（含小于全部、大于全部、夹在中间、正好存在）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [1, 3, 5, 6] 和 target = 2。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。2 不在数组里，最终 lo = 1，正好是它应该插入的位置。