手机版
你好,游客 登录 注册
背景:
阅读新闻

Java实现二分查找算法

[日期:2018-02-12] 来源:Linux社区  作者:morethink [字体: ]

二分查找(binary search),也称折半搜索,是一种在 有序数组查找某一特定元素 的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

  • 时间复杂度:折半搜索每次把搜索区域减少一半,时间复杂度为O(log n)。(n代表集合中元素的个数)
  • 空间复杂度: O(1)。虽以递归形式定义,但是尾递归,可改写为循环。

代码描述

递归

intbinarysearch(int array[], int low, int high, int target) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (array[mid] > target)
        return binarysearch(array, low, mid - 1, target);
    if (array[mid] < target)
        return binarysearch(array, mid + 1, high, target);
    return mid;
}

非递归

intbsearchWithoutRecursion(int a[], int key) {
    int low = 0;
    int high = a.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] > key)
            high = mid - 1;
        else if (a[mid] < key)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

二分查找法的缺陷

二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上:必须有序,我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序,可是又落到了第二个瓶颈上:它必须是数组。

数组读取效率是O(1),可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。

解决这些缺陷问题更好的方法应该是使用二叉查找树了,最好自然是自平衡二叉查找树了,既能高效的(O(n log n))构建有序元素集合,又能如同二分查找法一样快速(O(log n))的搜寻目标数。

本文永久更新链接地址http://www.linuxidc.com/Linux/2018-02/1509066.htm

linux
相关资讯       二分查找  二分查找算法 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款