java常见算法二分查找

二分查找，也称为折半查找，是一种高效的查找算法，它的时间复杂度为 O(log n)。二分查找要求被查找的数据结构必须有序。

在Java中，实现二分查找可以采用循环或递归两种方式。

以下是Java中的二分查找算法实现示例：

// 循环实现二分查找
public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 没有找到目标元素，返回-1
}

// 递归实现二分查找
public static int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) {
        return -1; // 没有找到目标元素，返回-1
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearch(arr, target, mid + 1, right);
    } else {
        return binarySearch(arr, target, left, mid - 1);
    }
}

这里的 arr 表示被查找的数组，target 表示要查找的目标元素，left 和 right 分别表示当前查找区间的左右边界。循环实现中使用了 while 循环，不断缩小查找区间，直到找到目标元素或者区间为空。递归实现中则使用了递归函数，每次递归缩小查找区间，直到找到目标元素或者区间为空。

以下是一个完整的示例代码，包括了循环和递归两种实现方式以及测试代码：

public class BinarySearch {

    // 循环实现二分查找
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 没有找到目标元素，返回-1
    }

    // 递归实现二分查找
    public static int binarySearch(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // 没有找到目标元素，返回-1
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearch(arr, target, mid + 1, right);
        } else {
            return binarySearch(arr, target, left, mid - 1);
        }
    }

    // 测试代码
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 7;

        int index1 = binarySearch(arr, target);
        int index2 = binarySearch(arr, target, 0, arr.length - 1);

        System.out.println("循环实现：目标元素的索引为 " + index1);
        System.out.println("递归实现：目标元素的索引为 " + index2);
    }
}

在测试代码中，我们定义了一个有序数组 arr 和要查找的目标元素 target，然后分别使用循环和递归两种方式来查找目标元素的索引，最后输出结果。

需要注意的是，在使用递归实现时，需要传入查找区间的左右边界，即 left 和 right，而在使用循环实现时，则可以通过初始化 left 和 right 来定义初始查找区间。

此外，二分查找算法还有一些变体，比如可以返回目标元素的第一个出现位置或最后一个出现位置，也可以在数组中插入目标元素。这些变体可以通过稍微修改上面的代码来实现。

好的，下面我再介绍一下二分查找算法的几个重要性质。

二分查找要求被查找的数组必须是有序的。

因为二分查找是通过比较目标元素与数组中间元素的大小来不断缩小查找区间的，如果数组无序，则无法保证中间元素的大小与目标元素的大小之间的关系，从而无法正确缩小查找区间，最终可能无法找到目标元素。

二分查找的时间复杂度为 O(log n)。

因为每次比较都能将查找区间缩小一半，所以最多需要进行 log n 次比较才能找到目标元素。因此，二分查找的时间复杂度为 O(log n)，是一种非常高效的查找算法。

二分查找的空间复杂度为 O(1)。

因为二分查找只需要保存数组的首尾指针和中间指针，所以空间复杂度为常量级别。

二分查找只适用于静态数据结构，即数据结构的元素不会频繁地被插入或删除。

因为如果数据结构中的元素频繁变动，就无法保证数据结构的有序性，从而无法使用二分查找算法。如果需要在动态数据结构中进行查找操作，可以考虑使用其他查找算法，比如散列表等。

二分查找的缺点是需要额外的空间来存储数据结构。

因为二分查找要求数据结构必须有序，所以在构建数据结构时需要额外的空间来保存有序的数据。如果空间有限，可能需要考虑其他的查找算法。

希望以上介绍能够对你理解二分查找算法有所帮助。

原文链接：codingdict.net

java常见算法二分查找

热门标签