Java实现二分查找算法_java 二分查找算法

二分查找（Binary Search）是一种高效的查找算法，适用于在有序数组中快速定位目标值。相比于线性查找，二分查找能够显著减少查找时间复杂度，从O(n)降低到O(log n)。本文将详细介绍二分查找算法的原理，并给出Java实现代码。

一、二分查找算法原理

二分查找算法的基本思路如下：

1. 初始化：设定数组的左右边界left和right，初始时分别为数组的起始和结束位置。
2. 查找中点：计算中点mid的位置，mid = left + (right - left) / 2。
3. 比较中点值：
   • 如果目标值等于mid位置的元素，则查找成功，返回mid。
   • 如果目标值小于mid位置的元素，则缩小查找范围到数组左半部分，即调整right = mid - 1。
   • 如果目标值大于mid位置的元素，则缩小查找范围到数组右半部分，即调整left = mid + 1。
4. 重复步骤2和3：直到找到目标值或查找范围为空（left > right）。

二、Java实现代码

下面是Java实现二分查找算法的代码：

public class BinarySearch {
    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;
        int result = binarySearch(sortedArray, target);
        
        if (result != -1) {
            System.out.println("目标值 " + target + " 在数组中的索引位置是：" + result);
        } else {
            System.out.println("目标值 " + target + " 不在数组中。");
        }
    }
    
    /**
     * 二分查找算法
     * 
     * @param array 有序数组
     * @param target 目标值
     * @return 目标值的索引位置，若不存在则返回-1
     */
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1; // 目标值不存在于数组中
    }
}

三、代码解析

1. binarySearch 方法：接受两个参数——有序数组和目标值，返回目标值在数组中的索引位置。如果目标值不存在于数组中，则返回-1。
2. 初始化左右边界：left 初始化为0，right 初始化为数组长度减1。
3. 循环查找：在left 小于等于 right 的条件下，不断计算中点 mid，并根据目标值与 mid 位置元素的比较结果调整 left 和 right。
4. 返回结果：如果找到目标值，则返回其索引位置；如果查找范围为空（left > right），则返回-1。

四、总结

二分查找算法是一种高效的查找方法，尤其适用于大规模有序数据集。通过不断缩小查找范围，二分查找能够在对数时间内定位目标值。掌握并理解二分查找算法，对提高算法设计和编程能力具有重要意义。

希望本文对你理解和实现二分查找算法有所帮助！如果有任何疑问或建议，欢迎在评论区留言。