如何使用Java函数实现二分搜索算法

二分搜索算法的本质是通过将数据分成两半，比较中间值和目标值来确定目标值的位置。因此，二分搜索算法是一种高效的搜索技术，尤其适用于有序列表或数组。在本文中，我们将学习如何使用Java函数实现二分搜索算法。

二分搜索算法的基本思路是不断将待查找区间一分为二，然后根据中间位置的值判断是否继续向左或向右逼近目标值。在 Java 中，我们可以使用以下代码实现二分搜索算法：

Java 代码：

public static int binarySearch(int[] sortedArray, int target) {
    int left = 0;
    int right = sortedArray.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (sortedArray[mid] == target) {
            return mid;
        } else if (sortedArray[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

上面的代码实现了一个二分搜索算法，通过接收一个已排序的整型数组和目标值来查找目标值的位置。该算法的时间复杂度为 O(logN)，其中 N 表示数组元素个数。

上述 Java 代码中，我们首先获取数组的左右两端作为待查找区间的初始范围。接着，在 while 循环中，我们用 mid 变量来记录区间的中间位置。如果 mid 对应的值等于目标值，则返回 mid 的位置。否则，如果 mid 对应的值小于目标值，则更新左边界 left 为 mid + 1；如果 mid 对应的值大于目标值，则更新右边界 right 为 mid - 1。经过多次循环，如果找到了目标值，则返回其位置；否则返回 -1，表示未找到。

在实际应用中，我们可以将上面的算法封装成一个函数，并适用于不同的数据类型和数据结构，如下：

Java 代码：

public static <T extends Comparable<T>> int binarySearch(T[] sortedArray, T target) {
    int left = 0;
    int right = sortedArray.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        int cmp = sortedArray[mid].compareTo(target);

        if (cmp == 0) {
            return mid;
        } else if (cmp < 0) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

上述代码使用泛型 T 来支持各种数据类型。我们在函数定义中使用 extends 关键字来声明 T 必须是相应类型的子类，以支持 compareTo() 方法的调用。此外，我们在调用 compareTo() 方法后，通过返回结果 cmp 的正负值来判断目标值在左侧或右侧区间，从而更新查找范围。

在函数调用时，我们可以传入一个已排序的数组和目标值，例如：

Java 代码：

Integer[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int position = binarySearch(array, 6); // position = 5

上述代码从整型数组中查找数字 6，并返回其位置。如果未找到，则返回 -1。由于该算法的复杂度比线性查找算法低得多，因此在大型数据集上，二分搜索算法具有更高的效率和更短的搜索时间。