Java中如何实现二分查找的函数？

二分查找，也称为折半查找或是二分法查找，它是一种高效的查找算法。该算法利用分治思想，将查找范围逐步缩小，找到目标元素。Java语言中实现该算法的函数可以采用递归和非递归的方式，下文将分别介绍二分查找的递归和非递归的实现。

一、递归实现

二分查找使用递归实现时，需要使用一个递归函数。该函数接受4个参数：要查找的数组、待查找的元素、起始位置和结束位置。递归实现的算法如下：

public static int binarySearch(int[] array, int target, int low, int high) {
    //判断起始位置是否大于等于结束位置
    if (low <= high) {
        //计算数组中间位置
        int mid = (low + high) / 2;
       
        //如果中间位置的元素与待查找元素相等
        if (array[mid] == target) {
            return mid;
        } 
        //如果中间位置元素比待查找元素大
        else if (array[mid] > target) {
            //在起始位置到mid-1的范围内继续查找
            return binarySearch(array, target, low, mid - 1);
        } 
        //如果中间位置元素比待查找元素小
        else {
            //在mid+1到结束位置的范围内继续查找
            return binarySearch(array, target, mid + 1, high);
        }
    } 
    //如果起始位置大于结束位置，说明未找到
    else {
        return -1;
    }
}

该函数的基本思想是：每次将待查找的区域缩小一半，因为数组是排好序的，如果要查找的元素比中间位置小，那么就查找左半部分的数组，否则就查找右半部分。如此一来，整个查找过程的时间复杂度为 O(log n)。

二、非递归实现

二分查找在Java中也可以使用非递归的方式进行实现，非递归实现主要依靠while循环的语句来控制查找过程。非递归实现的算法如下：

public static int binarySearch(int[] array, int target) {
    int low = 0, high = array.length - 1;
    //如果起始位置小于等于结束位置就开始查找
    while (low <= high) {
        //计算中间位置
        int mid = (low + high) / 2;
        //如果中间位置的元素与待查找元素相等
        if (array[mid] == target) {
            return mid;
        } 
        //如果中间位置元素比待查找元素大
        else if (array[mid] > target) {
            //在起始位置到mid-1的范围内继续查找
            high = mid - 1;
        } 
        //如果中间位置元素比待查找元素小
        else {
            //在mid+1到结束位置的范围内继续查找
            low = mid + 1;
        }
    }
    //如果起始位置大于结束位置，说明未找到
    return -1;
}

该函数的实现方式与递归算法基本相同，但函数没有采用递归的方式，每次确定待查找范围的中间位置后，根据中间位置元素与待查找元素的大小关系，调整待查找范围，并通过while循环一直查找到目标元素或查找范围为空为止。

总结

二分查找算法在Java中实现有递归和非递归两种方式。无论是哪种方式，实现的代码都比较简洁，查找速度快，并且其时间复杂度为 O(log n)，是比较高效和经典的算法。需要注意的是，对于使用二分查找的数组必须是排好序的，否则无法得到正确的结果。