教程文档【免费下载链接】30-seconds-of-codeCoding articles to level up your development skills项目地址https://gitcode.com/gh_mirrors/30/30-seconds-of-code点击查看免费下载本篇技术指南以 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 0, r arr.length - 1定义搜索区间 [l, r]覆盖整个数组循环条件while (l r)区间非空时持续收缩取中点const mid Math.floor((l r) / 2)计算中间索引注意防溢出写法在数组长度极大时可用l Math.floor((r - l) / 2)替代命中返回if (arr[mid] item) return mid值恰好存在其索引即插入位调整左界if (arr[mid] item) l mid 1目标值更大插入位置必在右半区调整右界else r mid - 1目标值更小插入位置必在左半区返回插入位return l循环结束时l即第一个不小于item的位置为什么返回左边界 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三个变量无额外内存开销。使用本实现需注意以下边界与前提数组必须预先按升序排列。与 binary-search.md 中的实现一致该算法依赖有序性对乱序数组不保证正确结果。不处理重复值。原文档明确说明该实现不处理数组中的重复元素当数组中存在多个与item相等的值时返回的可能是其中任意一个索引而不是稳定的最左或最右插入位置。若需在重复值场景下精确定位可参考 insertion-index-in-sorted-array.md 中基于findLastIndex()的lastInsertionIndex思路或对二分查找做等值分支收敛的变体。空数组与单元素数组。空数组时l 0, r -1循环不执行直接返回0单元素数组则取决于该元素与item的大小关系均能给出正确插入位。仅适用于数值或可比大小的元素。与insertionIndex基于比较函数的通用方案不同本实现针对数字数组直接使用、比较如需处理对象数组应扩展为传入比较函数的形式。与仓库其他方案的横向对比仓库中围绕有序数组插入索引存在多套方案可按下表选型方案来源文档时间复杂度适用场景insertionIndexfindIndexinsertion-index-in-sorted-array.mdO(n)小数组、需兼容升序/降序、代码最简lastInsertionIndexfindLastIndexinsertion-index-in-sorted-array.mdO(n)需返回最高插入位重复值靠右insertionIndexBy比较函数insertion-index-in-sorted-array.mdO(n)对象数组、自定义排序规则searchInsert二分查找binary-search-insert-index-sorted-number-array.mdO(log n)大型升序数字数组、算法题场景需要留意的是原文档中的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的技巧你便能在排序相关的查找与插入问题中自如切换到对数级别的解法。赞分享教程文档【免费下载链接】30-seconds-of-codeCoding articles to level up your development skills项目地址https://gitcode.com/gh_mirrors/30/30-seconds-of-code点击查看免费下载相关推荐61维观测契约Microduck RL如何实现多个策略运行时热切换61维观测契约Microduck RL如何实现多个策略运行时热切换 Microduck RL 是一个基于 mjlabMuJoCo Warp PPO的强教程文档mini.nvim 维护者指南从日常变更到双分发发布的全流程实践mini.nvim 维护者指南从日常变更到双分发发布的全流程实践 本文以 MAINTAINING.md https://link.gitcode.com/i/教程文档es-toolkit/compat 的 sortedIndex用二分查找确定有序数组插入位置es toolkit/compat 的 sortedIndex用二分查找确定有序数组插入位置 sortedIndex 是 es toolkit 在 Lodas前端后端上一篇DLSS Swapper指南如何管理并切换已安装游戏的DLSS版本下一篇黑苹果装前必做用 OpenCore-Simplify 硬件兼容性检测3 分钟判断你的电脑能不能装创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考