 追踪每一次折半的搜索路径)
freeCodeCamp「实现二分查找」挑战详解用 O(log n) 追踪每一次折半的搜索路径【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp本篇指南基于 freeCodeCamp 课程「Coding Interview Prep / Algorithms」板块中的 Implement Binary Search 编程题挑战 id61abc7ebf3029b56226de5b6。该题要求你实现一个在有序整数数组上进行二分查找的函数binarySearch并返回查找过程中每一步取到的中间值构成的搜索路径目标值必须是路径的最后一个元素若目标不存在则返回字符串Value Not Found。读完本文你将掌握二分查找的 O(log n) 效率来源、折半取中点时Math.floor()的确定性约定、官方测试数组上每条路径的逐步推演以及仓库内官方参考解答的完整实现逻辑与边界处理。挑战在课程中的位置与题目规格该题文件位于 Implement Binary Search其 YAML 元信息声明id: 61abc7ebf3029b56226de5b6 title: Implement Binary Search challengeType: 1 forumTopicId: 487618 dashedName: implement-binary-search从课程结构文件 algorithms.json 可以看到algorithms块按challengeOrder依次编排了 Find the Symmetric Difference、Inventory Update、Pairwise以及 Implement Bubble Sort / Selection Sort / Insertion Sort / Quick Sort / Merge Sort 五道排序题Implement Binary Search 正是该块的最后一道题第 10 题。该块又隶属于 superblock coding-interview-prep.jsonblocks: [algorithms, data-structures, take-home-projects]的第一块blockLayout为legacy-challenge-list即旧版经典编码题的列表式布局。challengeType: 1对应 freeCodeCamp 的编程题类型题面# --description-- 要求# --instructions-- 一组assert断言测试# --hints-- 初始代码骨架# --seed--/--seed-contents-- 官方参考答案# --solutions--。课程对挑战文件的字段合法性由 challenge-schema.js 中的 Joi schema 校验如dashedName必须匹配^[a-z0-9-]$、challengeType取值 0–33 等这保证了挑战文件能被解析器challenge-parser一致地消费。算法原理为什么折半是 O(log n)题目描述# --description--节给出的标准步骤如下找到有序数组的中间value。若value target返回true找到目标搜索结束。若中间value target下一步在数组的右半部分继续比较。若中间value target下一步在数组的左半部分继续比较。若搜索完整数组仍未找到返回false数组已搜完目标不存在。每一步比较后候选区间长度都变为原来的一半向下取整因此最多只需约log2(n)次比较就能穷尽或命中——这就是 O(log n) 效率的来源。与algorithms块前五道排序题O(n²) 的气泡/选择/插入排序、O(n log n) 的快排/归并排序形成对照排序题关注如何把无序变有序本题则关注在有序前提下如何最快定位二者共同构成面试算法基础。本挑战与教科书式二分的不同点在于题目要求展示你的工作过程show your work——不是只回答找到/没找到而是返回一路上每次折半取到的中间值序列搜索路径目标值必须是该数组的最后一个元素。函数规格与确定性约定来自# --instructions--节的完整要求函数签名binarySearch(searchList, value)输入一个有序整数数组和一个目标值。返回值一个数组按顺序in-order包含每次折半时找到的中间值直到找到目标目标值必须是返回数组的最后一个元素。若目标不存在返回字符串Value Not Found。示例binarySearch([1,2,3,4,5,6,7], 5)应返回[4,6,5]。硬性约定折半做除法时必须使用Math.floor()Math.floor(x/2)以此保证路径一致、可测试。这个约定非常重要二分查找在中点定义上有floor((LR)/2)与ceil((LR)/2)等多种等价写法它们找到目标的速度相同但途经的中间值序列会不同。测试只认一种确定的取法因此题目把中点计算方式钉死使断言可以精确到具体路径。测试使用的数组题目注明所有断言基于同一个 24 元素数组注意 6 缺失、5 与 8 之间有空洞70 是右端最大值const testArray [ 0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 49, 70 ];初始中点为Math.floor((24 - 1) / 2) 11即testArray[11] 13。这也解释了为什么几乎所有测试路径都以 13 开头。官方断言测试逐条推演# --hints--节共 7 组断言。先确认函数存在assert.isFunction(binarySearch);随后是 6 条路径断言下面结合 L / M / R左右边界与中点下标逐步验证帮助理解路径是怎么来的1)binarySearch(testArray, 0)应返回[13, 5, 2, 0]assert.deepEqual(binarySearch(_testArray, 0), [13, 5, 2, 0]);推演下标 0 起步骤LRM floor 计算中间值与目标 0 比较1023111313 0收缩到左半2010555 0继续左半304222 0继续左半40100命中路径[13, 5, 2, 0]成立。注意第 4 步 L0、R1 时中点取floor(1/2)0而非 0.5——这正是Math.floor约定的体现奇数宽度区间偏向左取中点。2)binarySearch(testArray, 1)应返回[13, 5, 2, 0, 1]前三步与目标 0 完全相同13 1、5 1、2 1 都向左到达 L0、R1、M0、中间值 0 时发现0 1收缩到L1, R1, M1中间值 1 命中。路径比目标 0 多一步[13, 5, 2, 0, 1]。3)binarySearch(testArray, 2)应返回[13, 5, 2]13 2 → 左5 2 → 左M2 处中间值 2 直接命中路径仅 3 个元素。这是中点直接就是目标的常见情形也对应目标 13见第 6 条那种一步命中的极端。4)binarySearch(testArray, 6)应返回Value Not Foundassert.strictEqual(binarySearch(_testArray, 6), Value Not Found);6 恰好落在数组的空洞里5 之后直接是 8。推演13 6 左M5 值 5 6 右L6, R10, M8值 10 6 左L6, R7, M6值 8 6 左L6, R5——此时right left区间为空宣告未找到。这条用例专门验证失败分支函数不能死循环、不能返回残缺数组必须返回指定字符串。5)binarySearch(testArray, 11)应返回[13, 5, 10, 11]13 11 左5 11 右L6, R10, M8, 值 1010 11 右L9, R10, M9, 值 99 11 右L10, R10, M10, 值 11命中。注意连续向右收缩时 L 每次1的推进方式。6)binarySearch(testArray, 13)应返回[13]首步中点 M11 就是 13一步命中路径只有目标本身。这验证了目标值必须是返回数组最后一个元素在最小情形下依然成立。7)binarySearch(testArray, 70)应返回[13, 19, 22, 49, 70]13 70 右L12, R23, M17, 值 1919 70 右L18, R23, M20, 值 2222 70 右L21, R23, M22, 值 23——等等23 不在答案中重新按官方解答的更新规则推right 23, left 21时middle left Math.floor((right-left)/2) 21 1 22值 23这里 23 ≠ 70继续L23, R23 不成立……实际官方路径为[13, 19, 22, 49, 70]即 L21, R23 时中点取 22值 23被跳过说明收缩逻辑中left middle 1后区间 [23,23] 取 M23 值 23关键在于23 70left 24会越界——官方解答此时middle 22 1 23? 不23 已在路径外。正确推演是22 70 →left 23, right 23middle 23 floor(0/2) 23值testArray[23]是 70查数组下标 22 是 23下标 23 是 49——数组共 24 个元素下标 0–23下标 22 23、下标 23 49、49 之后的 70……实际上该数组下标对应0→0, 1→1, …, 5→5, 6→8, 7→9, 8→10, 9→11, 10→12, 11→13, 12→14, 13→15, …, 20→22, 21→23, 22→49, 23→70。修正上面各步M11→13 ✓19 在下标 17 ✓M20→22 ✓22 70 → L21, R23, M21floor(2/2)22值 49 70 → L23, R23, M23值 70 命中。路径[13, 19, 22, 49, 70]与断言一致。此用例覆盖持续向右收缩直至数组末端的场景。下标与值的对应关系是手工推演路径时的核心依据建议读者在本地按上表逐条核对这正是本题展示路径训练意图所在。初始骨架与官方参考解答题目给出的起点--seed-contents--function binarySearch(searchList, value) { let arrayPath []; return arrayPath; }仓库内官方参考解答# --solutions--节箭头函数写法let binarySearch (searchList, value) { let arrayPath []; // set initial L - M - R let left 0; let right searchList.length - 1; let middle Math.floor(right / 2); // if first comparison finds value if (searchList[middle] value) { arrayPath.push(searchList[middle]); return arrayPath; } while (searchList[middle] ! value) { // add to output array arrayPath.push(searchList[middle]); // not found if (right left) { return Value Not Found; } // value is in left or right portion of array // update L - M - R if (searchList[middle] value) { right middle - 1; middle left Math.floor((right - left) / 2); } else { left middle 1; middle left Math.floor((right - left) / 2); } // if found update output array and exit if (searchList[middle] value) { arrayPath.push(searchList[middle]); break; } } return arrayPath; };从实现结构看官方解答有几个值得注意的取舍中点公式是相对区间长度而非(LR)/2收缩后统一用middle left Math.floor((right - left) / 2)初始则等价于Math.floor(right / 2)。两种写法在本题约束下产生同一条路径且都与题目要求的Math.floor折半一致。先记录、后收缩每轮循环先arrayPath.push(当前中间值)再判断right left终止再收缩并检查新中点是否命中。这个顺序保证了路径中每个中间值只出现一次、目标值恰好落在数组末尾——与题目目标值应为返回数组最后一个元素的规格一一对应。失败判定right left放在循环内部而非循环条件里这样即使区间先于命中变空也能在下一轮开头把最后一次无效中点计入路径后返回Value Not Found如目标 6 的情形。官方解答用了/!宽松比较。对整数数组这与严格比较等价如果你改写为自己的实现用更严谨测试同样可以通过断言只检查最终返回的数组或字符串。需要说明的一点官方解答属于教学示例性质——它对首步命中的处理单独提前避免重复 push对right left的检查在 push 之后执行。你的实现只要满足 7 条断言尤其是 6 →Value Not Found的失败路径和 13 →[13]的一步命中路径即为正确迭代、递归两种风格都可以。本地自测方法仓库内的挑战断言是随题目在 freeCodeCamp 编辑器中运行的但规格完整到可以直接在本地 Node 环境复现。把上面的testArray与 7 条assert拷入任意带assert的 Node 脚本即可验证const assert require(node:assert); const _testArray [ 0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 49, 70 ]; assert.isFunction(binarySearch); assert.deepEqual(binarySearch(_testArray, 0), [13, 5, 2, 0]); assert.deepEqual(binarySearch(_testArray, 1), [13, 5, 2, 0, 1]); assert.deepEqual(binarySearch(_testArray, 2), [13, 5, 2]); assert.strictEqual(binarySearch(_testArray, 6), Value Not Found); assert.deepEqual(binarySearch(_testArray, 11), [13, 5, 10, 11]); assert.deepEqual(binarySearch(_testArray, 13), [13]); assert.deepEqual(binarySearch(_testArray, 70), [13, 19, 22, 49, 70]); console.log(all pass);适用前提与限制本挑战假设输入数组已按升序排好且元素为整数不要求处理未排序输入或重复元素Math.floor中点约定只针对本套断言换成其他断言如ceil中点路径会不同。小结与延伸本题在algorithms块的排序五题之后压轴考察点可以归纳为三条理解区间折半为何带来 O(log n) 复杂度用 L / M / R 三指针维护并收缩搜索区间且中点计算遵循题目钉死的Math.floor规则以及把算法的中间状态每次中点值显式输出为可断言的路径覆盖一步命中13、多步左收缩0、1、2、未命中6与多步右收缩11、70五类典型轨迹。想继续深入可以在同一课程板块查看相邻的排序题——Implement Bubble Sort、Implement Merge Sort理解排序建立有序性与有序性支撑二分之间的完整链条。【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 freeCodeCamp「实现二分查找」挑战详解：用 O(log n) 追踪每一次折半的搜索路径
freeCodeCamp「实现二分查找」挑战详解用 O(log n) 追踪每一次折半的搜索路径【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp本篇指南基于 freeCodeCamp 课程「Coding Interview Prep / Algorithms」板块中的 Implement Binary Search 编程题挑战 id61abc7ebf3029b56226de5b6。该题要求你实现一个在有序整数数组上进行二分查找的函数binarySearch并返回查找过程中每一步取到的中间值构成的搜索路径目标值必须是路径的最后一个元素若目标不存在则返回字符串Value Not Found。读完本文你将掌握二分查找的 O(log n) 效率来源、折半取中点时Math.floor()的确定性约定、官方测试数组上每条路径的逐步推演以及仓库内官方参考解答的完整实现逻辑与边界处理。挑战在课程中的位置与题目规格该题文件位于 Implement Binary Search其 YAML 元信息声明id: 61abc7ebf3029b56226de5b6 title: Implement Binary Search challengeType: 1 forumTopicId: 487618 dashedName: implement-binary-search从课程结构文件 algorithms.json 可以看到algorithms块按challengeOrder依次编排了 Find the Symmetric Difference、Inventory Update、Pairwise以及 Implement Bubble Sort / Selection Sort / Insertion Sort / Quick Sort / Merge Sort 五道排序题Implement Binary Search 正是该块的最后一道题第 10 题。该块又隶属于 superblock coding-interview-prep.jsonblocks: [algorithms, data-structures, take-home-projects]的第一块blockLayout为legacy-challenge-list即旧版经典编码题的列表式布局。challengeType: 1对应 freeCodeCamp 的编程题类型题面# --description-- 要求# --instructions-- 一组assert断言测试# --hints-- 初始代码骨架# --seed--/--seed-contents-- 官方参考答案# --solutions--。课程对挑战文件的字段合法性由 challenge-schema.js 中的 Joi schema 校验如dashedName必须匹配^[a-z0-9-]$、challengeType取值 0–33 等这保证了挑战文件能被解析器challenge-parser一致地消费。算法原理为什么折半是 O(log n)题目描述# --description--节给出的标准步骤如下找到有序数组的中间value。若value target返回true找到目标搜索结束。若中间value target下一步在数组的右半部分继续比较。若中间value target下一步在数组的左半部分继续比较。若搜索完整数组仍未找到返回false数组已搜完目标不存在。每一步比较后候选区间长度都变为原来的一半向下取整因此最多只需约log2(n)次比较就能穷尽或命中——这就是 O(log n) 效率的来源。与algorithms块前五道排序题O(n²) 的气泡/选择/插入排序、O(n log n) 的快排/归并排序形成对照排序题关注如何把无序变有序本题则关注在有序前提下如何最快定位二者共同构成面试算法基础。本挑战与教科书式二分的不同点在于题目要求展示你的工作过程show your work——不是只回答找到/没找到而是返回一路上每次折半取到的中间值序列搜索路径目标值必须是该数组的最后一个元素。函数规格与确定性约定来自# --instructions--节的完整要求函数签名binarySearch(searchList, value)输入一个有序整数数组和一个目标值。返回值一个数组按顺序in-order包含每次折半时找到的中间值直到找到目标目标值必须是返回数组的最后一个元素。若目标不存在返回字符串Value Not Found。示例binarySearch([1,2,3,4,5,6,7], 5)应返回[4,6,5]。硬性约定折半做除法时必须使用Math.floor()Math.floor(x/2)以此保证路径一致、可测试。这个约定非常重要二分查找在中点定义上有floor((LR)/2)与ceil((LR)/2)等多种等价写法它们找到目标的速度相同但途经的中间值序列会不同。测试只认一种确定的取法因此题目把中点计算方式钉死使断言可以精确到具体路径。测试使用的数组题目注明所有断言基于同一个 24 元素数组注意 6 缺失、5 与 8 之间有空洞70 是右端最大值const testArray [ 0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 49, 70 ];初始中点为Math.floor((24 - 1) / 2) 11即testArray[11] 13。这也解释了为什么几乎所有测试路径都以 13 开头。官方断言测试逐条推演# --hints--节共 7 组断言。先确认函数存在assert.isFunction(binarySearch);随后是 6 条路径断言下面结合 L / M / R左右边界与中点下标逐步验证帮助理解路径是怎么来的1)binarySearch(testArray, 0)应返回[13, 5, 2, 0]assert.deepEqual(binarySearch(_testArray, 0), [13, 5, 2, 0]);推演下标 0 起步骤LRM floor 计算中间值与目标 0 比较1023111313 0收缩到左半2010555 0继续左半304222 0继续左半40100命中路径[13, 5, 2, 0]成立。注意第 4 步 L0、R1 时中点取floor(1/2)0而非 0.5——这正是Math.floor约定的体现奇数宽度区间偏向左取中点。2)binarySearch(testArray, 1)应返回[13, 5, 2, 0, 1]前三步与目标 0 完全相同13 1、5 1、2 1 都向左到达 L0、R1、M0、中间值 0 时发现0 1收缩到L1, R1, M1中间值 1 命中。路径比目标 0 多一步[13, 5, 2, 0, 1]。3)binarySearch(testArray, 2)应返回[13, 5, 2]13 2 → 左5 2 → 左M2 处中间值 2 直接命中路径仅 3 个元素。这是中点直接就是目标的常见情形也对应目标 13见第 6 条那种一步命中的极端。4)binarySearch(testArray, 6)应返回Value Not Foundassert.strictEqual(binarySearch(_testArray, 6), Value Not Found);6 恰好落在数组的空洞里5 之后直接是 8。推演13 6 左M5 值 5 6 右L6, R10, M8值 10 6 左L6, R7, M6值 8 6 左L6, R5——此时right left区间为空宣告未找到。这条用例专门验证失败分支函数不能死循环、不能返回残缺数组必须返回指定字符串。5)binarySearch(testArray, 11)应返回[13, 5, 10, 11]13 11 左5 11 右L6, R10, M8, 值 1010 11 右L9, R10, M9, 值 99 11 右L10, R10, M10, 值 11命中。注意连续向右收缩时 L 每次1的推进方式。6)binarySearch(testArray, 13)应返回[13]首步中点 M11 就是 13一步命中路径只有目标本身。这验证了目标值必须是返回数组最后一个元素在最小情形下依然成立。7)binarySearch(testArray, 70)应返回[13, 19, 22, 49, 70]13 70 右L12, R23, M17, 值 1919 70 右L18, R23, M20, 值 2222 70 右L21, R23, M22, 值 23——等等23 不在答案中重新按官方解答的更新规则推right 23, left 21时middle left Math.floor((right-left)/2) 21 1 22值 23这里 23 ≠ 70继续L23, R23 不成立……实际官方路径为[13, 19, 22, 49, 70]即 L21, R23 时中点取 22值 23被跳过说明收缩逻辑中left middle 1后区间 [23,23] 取 M23 值 23关键在于23 70left 24会越界——官方解答此时middle 22 1 23? 不23 已在路径外。正确推演是22 70 →left 23, right 23middle 23 floor(0/2) 23值testArray[23]是 70查数组下标 22 是 23下标 23 是 49——数组共 24 个元素下标 0–23下标 22 23、下标 23 49、49 之后的 70……实际上该数组下标对应0→0, 1→1, …, 5→5, 6→8, 7→9, 8→10, 9→11, 10→12, 11→13, 12→14, 13→15, …, 20→22, 21→23, 22→49, 23→70。修正上面各步M11→13 ✓19 在下标 17 ✓M20→22 ✓22 70 → L21, R23, M21floor(2/2)22值 49 70 → L23, R23, M23值 70 命中。路径[13, 19, 22, 49, 70]与断言一致。此用例覆盖持续向右收缩直至数组末端的场景。下标与值的对应关系是手工推演路径时的核心依据建议读者在本地按上表逐条核对这正是本题展示路径训练意图所在。初始骨架与官方参考解答题目给出的起点--seed-contents--function binarySearch(searchList, value) { let arrayPath []; return arrayPath; }仓库内官方参考解答# --solutions--节箭头函数写法let binarySearch (searchList, value) { let arrayPath []; // set initial L - M - R let left 0; let right searchList.length - 1; let middle Math.floor(right / 2); // if first comparison finds value if (searchList[middle] value) { arrayPath.push(searchList[middle]); return arrayPath; } while (searchList[middle] ! value) { // add to output array arrayPath.push(searchList[middle]); // not found if (right left) { return Value Not Found; } // value is in left or right portion of array // update L - M - R if (searchList[middle] value) { right middle - 1; middle left Math.floor((right - left) / 2); } else { left middle 1; middle left Math.floor((right - left) / 2); } // if found update output array and exit if (searchList[middle] value) { arrayPath.push(searchList[middle]); break; } } return arrayPath; };从实现结构看官方解答有几个值得注意的取舍中点公式是相对区间长度而非(LR)/2收缩后统一用middle left Math.floor((right - left) / 2)初始则等价于Math.floor(right / 2)。两种写法在本题约束下产生同一条路径且都与题目要求的Math.floor折半一致。先记录、后收缩每轮循环先arrayPath.push(当前中间值)再判断right left终止再收缩并检查新中点是否命中。这个顺序保证了路径中每个中间值只出现一次、目标值恰好落在数组末尾——与题目目标值应为返回数组最后一个元素的规格一一对应。失败判定right left放在循环内部而非循环条件里这样即使区间先于命中变空也能在下一轮开头把最后一次无效中点计入路径后返回Value Not Found如目标 6 的情形。官方解答用了/!宽松比较。对整数数组这与严格比较等价如果你改写为自己的实现用更严谨测试同样可以通过断言只检查最终返回的数组或字符串。需要说明的一点官方解答属于教学示例性质——它对首步命中的处理单独提前避免重复 push对right left的检查在 push 之后执行。你的实现只要满足 7 条断言尤其是 6 →Value Not Found的失败路径和 13 →[13]的一步命中路径即为正确迭代、递归两种风格都可以。本地自测方法仓库内的挑战断言是随题目在 freeCodeCamp 编辑器中运行的但规格完整到可以直接在本地 Node 环境复现。把上面的testArray与 7 条assert拷入任意带assert的 Node 脚本即可验证const assert require(node:assert); const _testArray [ 0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 49, 70 ]; assert.isFunction(binarySearch); assert.deepEqual(binarySearch(_testArray, 0), [13, 5, 2, 0]); assert.deepEqual(binarySearch(_testArray, 1), [13, 5, 2, 0, 1]); assert.deepEqual(binarySearch(_testArray, 2), [13, 5, 2]); assert.strictEqual(binarySearch(_testArray, 6), Value Not Found); assert.deepEqual(binarySearch(_testArray, 11), [13, 5, 10, 11]); assert.deepEqual(binarySearch(_testArray, 13), [13]); assert.deepEqual(binarySearch(_testArray, 70), [13, 19, 22, 49, 70]); console.log(all pass);适用前提与限制本挑战假设输入数组已按升序排好且元素为整数不要求处理未排序输入或重复元素Math.floor中点约定只针对本套断言换成其他断言如ceil中点路径会不同。小结与延伸本题在algorithms块的排序五题之后压轴考察点可以归纳为三条理解区间折半为何带来 O(log n) 复杂度用 L / M / R 三指针维护并收缩搜索区间且中点计算遵循题目钉死的Math.floor规则以及把算法的中间状态每次中点值显式输出为可断言的路径覆盖一步命中13、多步左收缩0、1、2、未命中6与多步右收缩11、70五类典型轨迹。想继续深入可以在同一课程板块查看相邻的排序题——Implement Bubble Sort、Implement Merge Sort理解排序建立有序性与有序性支撑二分之间的完整链条。【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考