知识卡片
二分查找需要空区间终止
有序数组查找中,比较目标与中点后,可排除不可能的一半,并在相等时返回位置。递归前还要处理left>right的空区间,表示未找到;原代码遗漏此分支,不能处理所有缺失目标。区间更新应排除中点,计算中点还需考虑索引加法的表示范围。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
确定新的查找区间,继续二分查找,具体方法如下。 如果data[middle].key大于key,由于data为有序线性表,可知data[middle…right].key均大于key,因此若表中存在关键字等于key的节点,则一定在位置middle左边的子表中。 反之,d
参考来源
- 位置:《代码精进之路:从码农到工匠(异步图书)》9.1.2 二分搜索(spine2;extracted/代码精进之路:从码农到工匠(异步图书)/_epub-src/OEBPS/text00001.html;u145-ch09-007)。
- 结论依据:原文在“确定新的查找区间”附近的定义、实例或代码支撑本卡的核心说明:有序数组查找中,比较目标与中点后,可排除不可能的一半,并在相等时返回位置。适用边界按该处前提解释,代码未执行。
- 原始内容:确定新的查找区间,继续二分查找,具体方法如下。 如果data[middle].key大于key,由于data为有序线性表,可知data[middle…right].key均大于key,因此若表中存在关键字等于key的节点,则一定在位置middle左边的子表中。 反之,d