Java算法探秘:二分查找详解

2023年 9月 12日 46.5k 0

当你需要在一个有序数组中查找特定元素时,二分查找是一种高效的算法。它的时间复杂度为 O(log n),相较于线性查找的 O(n),二分查找可以显著提高搜索效率。本文将详细解释什么是二分查找,以及如何在 Java 中实现它。

二分查找简介

二分查找,也称为折半查找,是一种在有序数组中查找目标元素的算法。它的原理是不断将查找范围减半,直到找到目标元素或确定目标元素不存在。二分查找的步骤如下:

  • 初始化左边界 left 为数组第一个元素的索引,右边界 right 为数组最后一个元素的索引。
  • 计算中间元素的索引 mid,它等于 (left + right) / 2。
  • 比较中间元素与目标元素:
    • 如果中间元素等于目标元素,则找到目标,返回中间元素的索引。
    • 如果中间元素大于目标元素,则将右边界更新为 mid - 1,继续在左半边查找。
    • 如果中间元素小于目标元素,则将左边界更新为 mid + 1,继续在右半边查找。
  • 重复步骤 2 和 3,直到找到目标元素或左边界超过右边界。
  • Java 实现二分查找

    以下是在 Java 中实现二分查找的示例代码:

    /**
     * 二分查找
     */
    public static int binarySearch(int[] intArr,int key){
        int left = 0;
        int right = intArr.length -1;
    
        while(left >> 1;
            //获取中间元素的值
            int midVal = intArr[mid];
            //比较中间元素和目标元素的值
            //如果中间元素小于目标元素,则将左边界更新为 mid + 1,继续在右半边查找。
            if (midVal  key)
                right = mid - 1;
            //如果中间元素等于目标元素,则找到目标,返回中间元素的索引。
            else
                return mid;
        }
    
        //如果循环结束仍未找到目标元素,返回一个负数,表示未找到,通常为-(left + 1)
        return -(left + 1);
    }
    
    public static void main(String[] args) {
    
        int[] intArray = new int[]{2,4,5,7,9,11,16,23,45,67};
    
        System.out.println(binarySearch(intArray,5));
        System.out.println(binarySearch(intArray,23));
        System.out.println(binarySearch(intArray,1));
        System.out.println(binarySearch(intArray,20));
        System.out.println(binarySearch(intArray,110));
    
    }
    

    输出结果为:

    2
    7
    -1
    -8
    -11
    

    上述代码中,binarySearch 方法接受一个有序数组 intArr 和目标元素 key 作为参数,然后使用二分查找算法在数组中查找目标元素的索引。如果找到目标元素,返回它的索引;否则,返回 负数 表示目标元素不存在。

    注意事项

    二分查找的前提是数组必须是有序的,否则无法正常工作。如果数组不是有序的,需要先对数组进行排序,然后才能使用二分查找算法。

    总结

    二分查找是一种高效的查找算法,适用于有序数组。它的时间复杂度为 O(log n),其中 n 是数组的长度。由于每次迭代都将搜索范围减半,因此它比线性查找等简单查找算法更加高效,特别是对于大型有序数组。通过仔细实现和理解二分查找算法,你可以在 Java 中轻松应用它来解决各种查找问题。

    相关文章

    JavaScript2024新功能:Object.groupBy、正则表达式v标志
    PHP trim 函数对多字节字符的使用和限制
    新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
    使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
    为React 19做准备:WordPress 6.6用户指南
    如何删除WordPress中的所有评论

    发布评论