知识卡片

普通读书笔记卡 · 6067.y

二分查找需要空区间终止

理解等级:中级

有序数组查找中,比较目标与中点后,可排除不可能的一半,并在相等时返回位置。递归前还要处理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