如何写一个Java函数实现二分查找

二分查找是一种基于比较的查找算法，也叫折半查找。它适用于有序数组和有序列表之类的数据结构。二分查找算法每次查找都将查找范围缩小一半，从而快速定位目标元素。本篇文章将介绍如何用Java实现二分查找算法。

1.算法流程

- 首先，需要将数组或者有序列表进行排序。

- 设定查找范围，即确定查找区间的左右边界。

- 将查找区间的中间元素与目标值进行比较。

- 如果中间元素小于目标值，则将查找范围调整为中间元素右侧的子数组，并重复步骤2和步骤3。

- 如果中间元素大于目标值，则将查找范围调整为中间元素左侧的子数组，并重复步骤2和步骤3。

- 如果中间元素等于目标值，返回该元素的下标。

- 如果查找范围缩小至左右边界重合，则退出查找，表示未找到目标元素。

2.代码实现

下面是一个使用Java实现二分查找算法的例子。要实现二分查找，我们需要编写一个函数，其输入为目标数组和需要查找的目标元素。以下是该函数实现的代码。

public static int binarySearch(int[] nums, int target) {
            int left = 0; // 左边界
            int right = nums.length - 1; // 右边界
            while (left <= right) {
                int mid = (left + right) / 2; // 中间位置
                if (target > nums[mid]) {
                    left = mid + 1; // 查找范围缩小为右边子数组
                } else if (target < nums[mid]) {
                    right = mid - 1; // 查找范围缩小为左边子数组
                } else {
                    return mid; // 目标元素在数组中找到，返回下标
                }
            }
            return -1; // 数组中没有目标元素，返回-1
}

3.测试

现在，测试一下上面的代码。让我们使用一个包含整数的数组，并在此数组中查找一个元素。我们将使用二分查找函数，并打印出查找元素的位置。

public static void main(String[] args) {
    int[] nums = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 11;
    int result = binarySearch(nums, target);
    if (result == -1) {
        System.out.println("目标元素 " + target + " 不在数组中");
    } else {
        System.out.println("目标元素 " + target + " 在数组中，下标为 " + result);
    }
}

输出应该为：目标元素 11 在数组中，下标为 5

4.时间复杂度

在最坏情况下，即要查找的元素不在数组中时，二分查找需要将查找范围逐步缩小直至左右边界重合，时间复杂度为 O(logn)。这是一种很快的算法，非常适用于大数据集合。