• 教程
• 文档

本篇技术指南以 binary-search-insert-index-sorted-number-array.md 为核心，讲解如何用二分查找（Binary Search）在有序数字数组中定位新元素的插入位置，将传统O(n)的线性查找优化为O(log n)。读完本文，你将掌握searchInsert的完整实现、左边界返回的算法原理，以及它与仓库中线性方案 insertion-index-in-sorted-array.md 的优劣对比，并能直接运用于 LeetCode 的 Search Insert Position 一类问题。

问题背景：为什么线性插入索引方案不够好

有序数组的价值在于它能够始终维持排序状态。但往有序数组中插入新元素，并不像简单地push到末尾那么容易——必须先找到正确的插入位置，保证插入后数组依然有序。

在 insertion-index-in-sorted-array.md 中，我们已经介绍过一种基于Array.prototype.findIndex()的方案：

const insertionIndex = (arr, n) => { const isDescending = arr[0] > arr[arr.length - 1]; const index = arr.findIndex(el => (isDescending ? n >= el : n <= el)); return index === -1 ? arr.length : index; }; insertionIndex([5, 3, 2, 1], 4); // 1 insertionIndex([30, 50], 40); // 1

该方案虽然简洁且能同时处理升序/降序数组，但Array.prototype.findIndex()是线性扫描，时间复杂度为O(n)，数组越大耗时越长。与之形成对比的是仓库中的 linear-search.md 所说明的线性查找特性：时间开销与数组规模成正比。

当面对 LeetCode 的Search Insert Position这类对复杂度有约束（O(log n)）的题目时，O(n)显然不是理想答案。这正是本文要解决的问题：用二分查找把插入索引定位的时间复杂度压到O(log n)。

二分查找回顾：O(log n) 的搜索利器

在深入插入索引之前，先回顾仓库 binary-search.md 中讲解的经典二分查找算法：

const binarySearch = (arr, item) => { let l = 0, r = arr.length - 1; while (l <= r) { const mid = Math.floor((l + r) / 2); const guess = arr[mid]; if (guess === item) return mid; if (guess > item) r = mid - 1; else l = mid + 1; } return -1; }; binarySearch([1, 2, 3, 4, 5], 1); // 0 binarySearch([1, 2, 3, 4, 5], 5); // 4 binarySearch([1, 2, 3, 4, 5], 6); // -1

该算法的工作原理是：维护搜索区间的左右边界，每次取中间元素与目标比较，将搜索区间对半缩小，直到找到目标或区间为空。其核心前提是数组必须预先有序。

作为参考，仓库 linear-search.md 中的线性查找时间复杂度为O(n)，即耗时与数组规模成正比；而二分查找为O(log n)，数组每扩大一倍，最多只增加一次比较。两者在大型数组上的性能差距是指数级的。

searchInsert 核心实现：只改一处 return

二分查找的目标是"找到给定元素的索引"，而本文要解决的是"找到插入新元素后仍保持有序的位置"。两者本质相似，只需对算法做小幅调整：若在区间收缩过程中恰好命中相同值，直接返回该值索引；否则在循环终止后返回左边界l，它正是新元素的应插入位置。

const searchInsert = (arr, item) => { let l = 0, r = arr.length - 1; while (l <= r) { const mid = Math.floor((l + r) / 2); if (arr[mid] === item) return mid; if (arr[mid] < item) l = mid + 1; else r = mid - 1; } return l; }; searchInsert([1, 3, 5, 6], 5); // 2 searchInsert([1, 3, 5, 6], 2); // 1 searchInsert([1, 3, 5, 6], 7); // 4

与原版binarySearch相比，函数体唯一实质性的改动就是末尾的return语句：不再返回-1，而是返回搜索区间的左边界l。下面逐行拆解：

为什么返回左边界 l 就是正确的插入索引

这是整个算法的关键所在。当while循环以l > r终止时，说明目标值在数组中不存在。此时需要考察不变量：在整个循环过程中，arr[l - 1]始终小于item（若l > 0），而arr[r + 1]始终大于item（若r < arr.length - 1）。

用测试用例验证：

• searchInsert([1, 3, 5, 6], 2)：2 不存在。收缩过程最终得到l = 1, r = 0，此时arr[0] = 1 < 2 < arr[1] = 3，返回l = 1，插入后数组为[1, 2, 3, 5, 6]，正确。
• searchInsert([1, 3, 5, 6], 7)：7 大于所有元素，区间一路右移，终止时l = 4（等于arr.length），插入到末尾，正确。
• 对称地，若目标值小于所有元素，l会终止于0，插入到开头，同样正确。

这一性质从代码结构上可以严格推断：每次移动l时都保证arr[l - 1] < item，每次移动r时都保证arr[r + 1] > item，循环终止时二者相邻，l便落在"大于等于item的第一个位置"上。

复杂度与边界条件分析

时间复杂度O(log n)：每轮迭代将区间减半，最多执行⌊log₂n⌋ + 1次比较，优于findIndex()方案的O(n)，完全满足 LeetCode 同类题目对O(log n)的复杂度约束。空间复杂度O(1)：仅使用l、r、mid三个变量，无额外内存开销。

使用本实现需注意以下边界与前提：

1. 数组必须预先按升序排列。与 binary-search.md 中的实现一致，该算法依赖有序性，对乱序数组不保证正确结果。
2. 不处理重复值。原文档明确说明，该实现不处理数组中的重复元素：当数组中存在多个与item相等的值时，返回的可能是其中任意一个索引，而不是稳定的最左或最右插入位置。若需在重复值场景下精确定位，可参考 insertion-index-in-sorted-array.md 中基于findLastIndex()的lastInsertionIndex思路，或对二分查找做等值分支收敛的变体。
3. 空数组与单元素数组。空数组时l = 0, r = -1，循环不执行，直接返回0；单元素数组则取决于该元素与item的大小关系，均能给出正确插入位。
4. 仅适用于数值（或可比大小）的元素。与insertionIndex基于比较函数的通用方案不同，本实现针对数字数组直接使用<、>比较，如需处理对象数组，应扩展为传入比较函数的形式。

与仓库其他方案的横向对比

仓库中围绕"有序数组插入索引"存在多套方案，可按下表选型：

需要留意的是，原文档中的insertionIndex通过arr[0] > arr[arr.length - 1]松散地判断数组升降序，并未严格校验整个数组的有序性；而searchInsert则直接假设输入为升序数组。两类方案都适用于学习演示，生产环境还应结合Array.prototype.sort()或库函数做好前置排序与入参校验。

实战验证：从测试用例到算法题

searchInsert的实现可直接用于 LeetCodeSearch Insert Position（返回目标值索引或应插入位置）等经典题目。撰写或调试此类代码时，建议覆盖以下测试矩阵：

// 目标值存在 searchInsert([1, 3, 5, 6], 5); // 2 —— 恰好命中，返回真实索引 searchInsert([1, 3, 5, 6], 1); // 0 —— 命中最小元素 // 目标值不存在（插入区间内部） searchInsert([1, 3, 5, 6], 2); // 1 searchInsert([1, 3, 5, 6], 4); // 2 // 目标值越界 searchInsert([1, 3, 5, 6], 0); // 0 —— 插入到最前 searchInsert([1, 3, 5, 6], 7); // 4 —— 插入到末尾 // 边界输入 searchInsert([], 1); // 0 —— 空数组 searchInsert([1], 0); // 0 searchInsert([1], 2); // 1

在 30 seconds of code 仓库中，该文档被收录于 content/collections/js/algorithm.yaml 所定义的 JavaScript 算法集合（标签algorithm、array、math），作为二分查找专题的延伸篇，与 binary-search.md（基础二分查找）、linear-search.md（线性查找对照）、insertion-index-in-sorted-array.md（线性插入索引方案）共同构成一条完整的查找与插入算法学习链路。

小结

本文以"在有序数字数组中二分定位插入索引"为主线，完整呈现了searchInsert的实现：通过复用二分查找的区间收缩循环、仅在终止时返回左边界l，将插入索引问题的时间复杂度从O(n)优化到O(log n)。相比findIndex()线性方案，它在大型数组与算法题场景下优势显著；同时需谨记其升序前提与不处理重复值的限制。掌握了这个"只改一处 return"的技巧，你便能在排序相关的查找与插入问题中自如切换到对数级别的解法。

• 教程
• 文档