Java函数中如何实现二分搜索算法？

二分搜索（Binary Search）算法也被称为折半查找，它是一种高效的查找算法，应用广泛。在一个有序的数据结构中，二分搜索算法将目标值与数据结构中间的值进行比较，从而每次将查找范围缩小一半，最终找到目标值或者判定不存在。

在Java中，我们可以通过递归或非递归的方式实现二分搜索算法。下面我们将详细介绍这两种实现方式。

递归实现

递归实现比较简单，我们只需要判断目标值是否等于中间值，如果是则返回中间值的下标；如果目标值小于中间值，则在左侧继续进行二分搜索；如果目标值大于中间值，则在右侧继续进行二分搜索。

代码如下：

public static int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) {
        // 没找到
        return -1;
    }
    int mid = (left + right) / 2;
    if (arr[mid] == target) {
        // 找到了
        return mid;
    } else if (arr[mid] > target) {
        // 在左侧继续搜索
        return binarySearch(arr, target, left, mid - 1);
    } else {
        // 在右侧继续搜索
        return binarySearch(arr, target, mid + 1, right);
    }
}

需要注意的是，left和right表示搜索范围的左右边界，初始时left为0，right为数组长度减一。如果搜索范围中不存在目标值，则left会越过right，此时返回-1。

非递归实现

非递归实现需要使用循环，我们需要不断将搜索范围缩小一半，直到找到目标值或者判定不存在。

代码如下：

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            // 找到了
            return mid;
        } else if (arr[mid] > target) {
            // 在左侧继续搜索
            right = mid - 1;
        } else {
            // 在右侧继续搜索
            left = mid + 1;
        }
    }
    // 没找到
    return -1;
}

需要注意的是，非递归实现中的循环条件是left <= right，只要left越过right，搜索范围就不存在，退出循环并返回-1。

实现思路总结

从以上两个实现方式中，我们可以看到二分搜索算法的实现思路大致如下：

1. 选取有序数据结构的中间值。

2. 判断目标值与中间值的大小关系。

3. 如果目标值大于中间值，则在右侧继续进行二分搜索。

4. 如果目标值小于中间值，则在左侧继续进行二分搜索。

5. 如果目标值等于中间值，则返回中间值的下标。

6. 如果在搜索范围内没有找到目标值，则返回-1。

实现二分搜索算法时，需要注意以下几点：

1. 数据结构必须是有序的。

2. 二分搜索算法最好用非递归方式实现，因为递归方式可能会造成栈溢出。

3. 二分搜索算法通过选择合适的中间值，不断缩小搜索范围，从而达到高效的查找目的。

4. 二分搜索算法的时间复杂度为O(logn)，比线性搜索算法要快得多。

总结

通过以上介绍，我们了解了Java中实现二分搜索算法的两种方式：递归和非递归。无论哪种实现方式，其基本思路都是一致的，即通过选择中间值，不断缩小搜索范围，最终找到目标值或者判定不存在。二分搜索算法的时间复杂度为O(logn)，十分高效，应用十分广泛。