使用 Java 函数实现二分查找：一个简单的例子

二分查找又称折半查找，是一种效率比较高的查找算法，它的前提是数据必须有序，每次查找都通过将查找区间缩小一半来进行，直到查找到目标位置。本文将通过一个简单的例子来介绍如何使用 Java 函数实现二分查找。

思路分析

1. 输入目标值和有序数组

2. 设置起始位置和结束位置为数组起始和结束位置，计算出中间位置

3. 以中间位置为基准，判断目标值和中间值的大小，如果目标值大于中间值，则将起始位置设置为中间位置+1，如果目标值小于中间值，则将结束位置设置为中间位置-1

4. 如果目标值等于中间值，则返回中间位置

5. 如果起始位置等于结束位置但目标值不等于中间值，则说明数组中不存在目标值，返回-1

编写代码

下面是使用 Java 函数实现二分查找的代码：

public static int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        if (target == arr[mid]) {
            return mid;
        } else if (target > arr[mid]) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return -1;
}

测试代码

下面是测试代码：

public static void main(String[] args) {
    int[] arr = {1, 3, 5, 7, 9};
    
    int index1 = binarySearch(arr, 3); // index1 = 1
    int index2 = binarySearch(arr, 6); // index2 = -1
    
    System.out.println(index1);
    System.out.println(index2);
}

接下来我们来详细解释一下代码的实现。

在函数 binarySearch 中，我们需要传入两个参数：有序数组 arr 和目标值 target。我们首先要定义两个变量 low 和 high，它们分别表示有序数组的起始位置和结束位置。由于我们需要查找的是整个有序数组，因此起始位置为0，结束位置为数组长度减1。

接下来，我们需要进入查找循环。在查找循环中，我们需要判断起始位置和结束位置的大小关系：如果起始位置小于等于结束位置，则循环继续，否则循环退出。

在循环中，我们还需要定义一个变量 mid，它表示中间位置。计算 mid 的公式为 mid = (low + high) / 2。这里我们采用了整数相除的方式来计算 mid，因此我们不需要进行额外的类型转换。

接下来，我们需要根据目标值和中间值的大小关系来调整起始位置和结束位置。如果目标值等于中间值，则直接返回中间位置；否则，如果目标值大于中间值，则说明目标值在中间位置的右侧，因此将起始位置设置为中间位置+1；如果目标值小于中间值，则说明目标值在中间位置的左侧，因此将结束位置设置为中间位置-1。

如果在查找循环中未找到目标值，则说明数组中不存在该值，我们需要返回-1。

最后，我们可以使用上面的测试代码来验证我们的实现是否正确。在测试代码中，我们使用 arr 数组来构建一个有序数组，并分别使用 binarySearch 函数来查找3和6这两个数在 arr 数组中的位置。根据有序数组的定义，我们可以很容易地得到这两个数在数组中的位置：3应该在数组下标为1的位置，6不存在于数组中。因此，如果我们的实现正确，就应该输出1和-1这两个值。