两种java实现二分查找的方式

下面是详细讲解“两种java实现二分查找的方式”的攻略。

一、二分查找基本算法

二分查找算法的基本思想是：在一个有序数组中，查找一个元素，先找到数组的中间元素，然后将要查找的元素和中间元素进行比较，如果相等则直接返回中间元素，如果大于则在中间元素的右半部分继续查找，如果小于则在中间元素的左半部分继续查找，如此循环直到找到要查找的元素或者找不到为止。

Java实现二分查找基本算法的代码如下所示：

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

其中，arr是要查找的有序数组，val是要查找的元素的值，如果找到则返回元素在数组中的下标，否则返回-1。

二、递归实现二分查找

除了上面介绍的基本算法以外，还可以使用递归的方式实现二分查找。递归实现二分查找的代码如下所示：

public static int binarySearchRecursive(int[] arr, int val, int left, int right) {
    if (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == val) {
            return mid;
        } else if (arr[mid] < val) {
            return binarySearchRecursive(arr, val, mid + 1, right);
        } else {
            return binarySearchRecursive(arr, val, left, mid - 1);
        }
    }
    return -1;
}

其中，arr是要查找的有序数组，val是要查找的元素的值，left表示要查找的数组区间的左边界，right表示要查找的数组区间的右边界。如果找到则返回元素在数组中的下标，否则返回-1。

三、示例说明

下面我们来演示一下使用两种方式查找一个有序数组中的元素。

假如要查找数组arr中的元素val=4，其中arr的元素为[1, 2, 3, 4, 5, 6, 7, 8, 9]。使用基本算法查找的代码如下：

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int index = binarySearch(arr, 4);
System.out.println(index); // 输出：3

使用递归方式查找的代码如下：

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int left = 0;
int right = arr.length - 1;
int index = binarySearchRecursive(arr, 4, left, right);
System.out.println(index); // 输出：3

从输出结果可以看出，使用两种方式都能成功找到数组中的元素val=4。

四、总结

以上就是Java实现二分查找的两种方式的攻略，通过本攻略的介绍，读者可以了解到如何使用Java实现二分查找的基本算法和递归算法，并且可以通过示例了解到如何在具体应用场景中使用这两种算法来查找元素。

阅读剩余 40%