知识卡片
搜索返回索引零也是成功
bisearch按当前compare在有序数组中查目标,成功返回实际下标,未找到-1。下标0是有效成功,调用方不能用返回值当布尔值判断找到与否。它返回位置,不交还/移除对象或转移数据所有权。
接口接收元素数size和字节宽度esize、目标地址及比较器,实际源码target为const void*;表图少了const,按定义理解不修改目标。重复键时返回遇到的某个匹配位置,不保证第一个/最后一个,也不在失败时返回插入点。
本实现用switch仅列case−1、0、1,因而比较回调必须严格规范到这三值。通常只承诺负/零/正的回调若直接返回−7或12,将没有分支改变边界;不能把其他接口允许任意符号值的约定不经适配搬来。
223源码middle=(left+right)/2,合法范围之外还需注意整数求和/字节索引溢出;理论对半不保证所有机器整数规模都安全。比较检查次数通常按⌊log₂n⌋+1这类整数界表达,不是任意n恰好log₂n次。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
目标的索引值;否则,返回-1。 描述 利用二分查找定位sorted(一个包含有序元素的数组)中的target。数组中的元素个数由size决定,每个元素的大小由esize决定。函数指针compare指向一个用户定义的比较函数。如果key1>key2,函数返回1,如果key1=key2,函数返回0,如果
- · 查看原书依据
middle设置为left和right之间区域的中间值。如果处于middle的元素比目标值小,将左索引值移动到middle后一个元素的位置上。即下一组要搜索的区域是当前数据集的上半区。如果处于middle的元素比目标值大,将右索引值移动到middle前一个元素的位置上。即下一组要搜索的区域是当前数据