← 返回刚才阅读的位置

知识卡片

操作参考卡 · 5654.c.1.a.2.a.18 · 生成模型:未记录

搜索返回索引零也是成功

理解等级:中级

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前一个元素的位置上。即下一组要搜索的区域是当前数据

    参考来源

    - 位置:《算法精解:C语言描述》第12章《二分查找的接口定义》(spine1354;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1320.html;u222-ch12-019)。 - 结论依据:222全部返回/参数说明和02976原型、02978–02980实际const target与switch三case完整实读,明确索引职责及回调值域,不把接口要求满足时误报算法本身必错。 - 原始内容:目标的索引值;否则,返回-1。 描述 利用二分查找定位sorted(一个包含有序元素的数组)中的target。数组中的元素个数由size决定,每个元素的大小由esize决定。函数指针compare指向一个用户定义的比较函数。如果key1>key2,函数返回1,如果key1=key2,函数返回0,如果 - 位置:《算法精解:C语言描述》第12章《二分查找的实现与分析》(spine1355;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1321.html;u223-ch12-019)。 - 结论依据:223源码middle=(left+right)/2,合法范围之外还需注意整数求和/字节索引溢出;理论对半不保证所有机器整数规模都安全。比较检查次数通常按⌊log₂n⌋+1这类整数界表达,不是任意n恰好log₂n次。 - 原始内容:middle设置为left和right之间区域的中间值。如果处于middle的元素比目标值小,将左索引值移动到middle后一个元素的位置上。即下一组要搜索的区域是当前数据集的上半区。如果处于middle的元素比目标值大,将右索引值移动到middle前一个元素的位置上。即下一组要搜索的区域是当前数据