查找比较数

由沙吉布(K. Shajib)编辑:

我正在尝试跟踪此二进制搜索代码中的键比较次数。对于数组大小为的比较结果应为17左右2^16您能解释一下我为什么要33岁吗?

public class AdvancedBinarySearch {

    int count = 0;

    // Returns location of key, or -1 if not found 
    int AdvancedBinarySearch(int arr[], int l, int r, int x) {
        int m;

        while (r - l > 1) {
            count++;
            m = l + (r - l) / 2;
            if (arr[m] <= x) {
                l = m;
                count++;
            } else {
                r = m;
                count++;
            }
        }

        if (arr[l] == x) {
            count++;
            return l;
        }

        if (arr[r] == x) {
            count++;
            return r;

        } else {
            count++;
            return -1;

        }
    }

    public void setCount(int i) {
        this.count = i;
    }
}
吉恩·内尔(Jyon Nyre):

您的代码计算了if (arr[m] <= x)两次比较。如果您count++从下方l = m以及从下方删除r = m,则将不再发生。

我已经在此更改之前和之后进行了测试,并在从0到65535的整数数组中搜索189。此数组的大小为2 ^ 16,更改之前进行了33次比较,更改之后进行了17次比较被计算在内,因此我认为此更改可以完成您想要的操作。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

  1. 1

    来自Microsoft Office加载项taskpane.js的MySQL驱动程序模块的空引用

  2. 2

    使用AWS Cognito和React的仅限Facebook / Google的登录名(无用户名/密码)

  3. 3

    创建Windows Phone 8应用并将其连接到数据库的最佳方法(最好是SQL Server)

  4. 4

    为什么Java中的System.out.println()打印到控制台?

  5. 5

    卷曲函数无法解析来自bash中变量的代理

  6. 6

    是什么在Android的consumer-rules.pro和proguard-rules.pro之间的区别?

  7. 7

    设置与Apache POI Excel表散点图标记图标的颜色

  8. 8

    将Qt Pyside2与asyncio await语法一起使用?

  9. 9

    崇高的文字+蟒蛇的蟒蛇

  10. 10

    任务':app:minifyReleaseWithR8'.java.lang.NullPointerException的执行失败(无错误消息)

  11. 11

    OpenJDK的和AdoptOpenJDK的区别

  12. 12

    大型数据集缓存到Spark内存中时,“超出了GC开销限制”(通过sparklyr和RStudio)

  13. 13

    “执行测试CMAKE_HAVE_LIBC_PTHREAD”失败实际上是什么意思?

  14. 14

    使用Core 2.2中的Identity,如何在关闭浏览器15分钟后保持会话活动?

  15. 15

    React中的ForwardRefExoticComponent和ForwardRefRenderFunction有什么区别?

  16. 16

    猫鼬查找结果,然后将字段替换为findOne

  17. 17

    如何降级Google Colab的Torch版本

  18. 18

    Keras提前停止回调错误,val_loss指标不可用

  19. 19

    如何避免VSCode中的“导入路径不能以.ts扩展名结尾”错误?

  20. 20

    Nuxt.JS:如何在页面中获取路由URL参数

  21. 21

    是否有为什么会AccessibilityManager.sInstance导致内存泄漏的一个原因?

热门标签

归档