知识卡片
有序数组后继需先明确重复语义
若有序数据键互异、x确实存在且不是最大项,找到x下标后取下一项就是后继,总成本由定位的O(log n)支配。但最后一项没有后继,不能越界读取。
若允许重复键,“下一个数组项”可能仍等于x;若所求是严格大于x的最小值,应寻找第一个>x的位置,而不是在bisearch返回的任意匹配下标上简单加一。x不存在时也要先明确是否仍要找其上界,原接口返回−1不直接提供该位置。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
继任者是x结点之后的下一个最大的结点。例如,在一个有序数据集{24,39,41,55,87,92}中,41的继任者是55。用二分查找如何找到元素x的继任者?此操作的时间复杂度是多少? 答:在一个有序数据集中,用二分查找寻找x的继任者,首先要定位x元素。然后,只需要简单地向右移动一位,就找到了继任者。
参考来源
- 位置:《算法精解:C语言描述》第12章《问与答》(spine1357;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1323.html;u225-ch12-022)。
- 结论依据:225最后后继问答实读,结合222匹配不保证首/尾的源码语义补足条件,未实现未给出的upper-bound函数。
- 原始内容:继任者是x结点之后的下一个最大的结点。例如,在一个有序数据集{24,39,41,55,87,92}中,41的继任者是55。用二分查找如何找到元素x的继任者?此操作的时间复杂度是多少? 答:在一个有序数据集中,用二分查找寻找x的继任者,首先要定位x元素。然后,只需要简单地向右移动一位,就找到了继任者。