V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
KissFace
V2EX  ›  问与答

迫于考试,请教各位大佬一个 Java 二分查找算法

  •  
  •   KissFace · 2021-04-15 15:32:56 +08:00 · 185 次点击
    这是一个创建于 399 天前的主题,其中的信息可能已经有所发展或是发生改变。
    题目:给定一个递增排序的数组,查找某个数字是否在数组中,如果在数组中,则返回该数字在数组中第一次出现的位置(从 0 开始);如果不在数组中,返回-1 。务必使用二分查找的方式

    哪位好心人可以贴下代码
    第 1 条附言  ·  2021-04-16 13:52:22 +08:00
    此贴结
    beichenhpy
        1
    beichenhpy  
       2021-04-15 20:45:44 +08:00
    这不就是二分查找吗?百度一下都有
    beichenhpy
        2
    beichenhpy  
       2021-04-15 21:04:17 +08:00
    public static int binarySearch(int[] arrays, int key, int start, int end) {
    if (key < arrays[start] || key > arrays[end] || start > end) {
    return -1;
    }
    int mid = (start + end) / 2;
    if (arrays[mid] > key) {
    return binarySearch(arrays, key, start, mid - 1);
    } else if (arrays[mid] < key) {
    return binarySearch(arrays, key, mid + 1, end);
    } else {
    return mid;
    }
    }
    beichenhpy
        3
    beichenhpy  
       2021-04-15 21:06:32 +08:00
    jdk 的写法
    // Like public version, but without range checks.
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
    int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
    int mid = (low + high) >>> 1;
    int midVal = a[mid];

    if (midVal < key)
    low = mid + 1;
    else if (midVal > key)
    high = mid - 1;
    else
    return mid; // key found
    }
    return -(low + 1); // key not found.
    }
    KissFace
        4
    KissFace  
    OP
       2021-04-16 13:51:57 +08:00
    @beichenhpy 谢谢老哥
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3940 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 07:18 · PVG 15:18 · LAX 00:18 · JFK 03:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.