java二分查找的原理如何实现

发布时间：2022-06-01 16:26:10 作者：iii
来源：亿速云阅读：203

Java二分查找的原理如何实现

引言

在计算机科学中，查找算法是用于在数据集中定位特定元素的过程。二分查找（Binary Search）是一种高效的查找算法，适用于在有序数组中查找特定元素。本文将详细介绍Java中二分查找的原理及其实现方法。

二分查找的原理

二分查找的基本思想是将有序数组分成两半，通过比较中间元素与目标值的大小关系，逐步缩小查找范围，直到找到目标值或确定目标值不存在。

算法步骤

初始化：设定两个指针，low 和 high，分别指向数组的起始位置和结束位置。
计算中间位置：计算中间位置 mid，即 mid = low + (high - low) / 2。
比较中间元素：
- 如果中间元素等于目标值，则查找成功，返回中间位置。
- 如果中间元素大于目标值，则目标值在左半部分，将 high 更新为 mid - 1。
- 如果中间元素小于目标值，则目标值在右半部分，将 low 更新为 mid + 1。
重复步骤2和3：直到 low 大于 high，此时查找失败，返回 -1。

时间复杂度

二分查找的时间复杂度为 O(log n)，其中 n 是数组的长度。这是因为每次查找都将查找范围缩小一半，因此查找次数最多为 log₂n。

Java实现

下面是一个简单的Java实现二分查找的示例代码：

public class BinarySearch {

    // 二分查找方法
    public static int binarySearch(int[] array, int target) {
        int low = 0;
        int high = array.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (array[mid] == target) {
                return mid; // 找到目标值，返回索引
            } else if (array[mid] < target) {
                low = mid + 1; // 目标值在右半部分
            } else {
                high = mid - 1; // 目标值在左半部分
            }
        }

        return -1; // 未找到目标值
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 7;

        int result = binarySearch(array, target);

        if (result != -1) {
            System.out.println("目标值 " + target + " 在数组中的索引为: " + result);
        } else {
            System.out.println("目标值 " + target + " 不在数组中");
        }
    }
}

代码解析

binarySearch方法：
- low 和 high 分别表示当前查找范围的下界和上界。
- mid 是当前查找范围的中间位置。
- 通过比较 array[mid] 和 target 的大小关系，调整 low 或 high 的值，逐步缩小查找范围。
- 如果找到目标值，返回其索引；否则返回 -1。
main方法：
- 定义一个有序数组 array 和目标值 target。
- 调用 binarySearch 方法进行查找，并根据返回值输出结果。

二分查找的变种

在实际应用中，二分查找有多种变种，适用于不同的场景。以下是几种常见的变种：

1. 查找第一个等于目标值的元素

在某些情况下，数组中可能存在多个相同的目标值，我们需要找到第一个出现的索引。可以通过修改二分查找的条件来实现：

public static int binarySearchFirst(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (array[mid] >= target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    if (low < array.length && array[low] == target) {
        return low;
    } else {
        return -1;
    }
}

2. 查找最后一个等于目标值的元素

类似地，我们可以找到最后一个等于目标值的元素：

public static int binarySearchLast(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (array[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    if (high >= 0 && array[high] == target) {
        return high;
    } else {
        return -1;
    }
}

3. 查找第一个大于等于目标值的元素

在某些情况下，我们需要找到第一个大于或等于目标值的元素：

public static int binarySearchFirstGreaterOrEqual(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (array[mid] >= target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return low < array.length ? low : -1;
}

4. 查找最后一个小于等于目标值的元素

类似地，我们可以找到最后一个小于或等于目标值的元素：

public static int binarySearchLastLessOrEqual(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (array[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return high >= 0 ? high : -1;
}

总结

二分查找是一种高效的查找算法，适用于有序数组。通过不断缩小查找范围，二分查找能够在 O(log n) 的时间复杂度内找到目标值。本文介绍了二分查找的基本原理及其在Java中的实现方法，并探讨了几种常见的变种。掌握二分查找及其变种，对于解决实际编程问题具有重要意义。