Java 中的二分查找算法详解

简介

二分查找算法（Binary Search Algorithm）是一种高效的搜索算法，它在已排序的数据集中查找特定元素。相比于线性查找（逐个检查元素），二分查找的时间复杂度为 $O(log n)$，这使得它在处理大规模数据时表现更为出色。本文将详细介绍 Java 中二分查找算法的基础概念、使用方法、常见实践以及最佳实践。

基础概念

原理

二分查找的核心思想是将查找区间不断缩小一半，直到找到目标元素或确定目标元素不存在。具体步骤如下： 1. 确定查找区间的起始点（left）和结束点（right）。 2. 计算中间位置（mid）。 3. 将中间位置的元素与目标元素进行比较： - 如果中间元素等于目标元素，则查找成功，返回中间位置。 - 如果中间元素大于目标元素，则目标元素可能在左半部分，更新结束点为 mid - 1。 - 如果中间元素小于目标元素，则目标元素可能在右半部分，更新起始点为 mid + 1。 4. 重复步骤 2 和 3，直到查找区间为空（left > right），表示目标元素不存在。

条件

二分查找要求数据集必须是有序的，否则无法正确缩小查找区间。

使用方法

递归实现

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1; // 目标元素不存在
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid; // 找到目标元素
        } else if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target); // 在左半部分继续查找
        } else {
            return binarySearch(arr, mid + 1, right, target); // 在右半部分继续查找
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int result = binarySearch(arr, 0, arr.length - 1, target);
        if (result != -1) {
            System.out.println("目标元素 " + target + " 的索引是: " + result);
        } else {
            System.out.println("目标元素 " + target + " 不存在。");
        }
    }
}

迭代实现

public class BinarySearchIterative {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid; // 找到目标元素
            } else if (arr[mid] > target) {
                right = mid - 1; // 在左半部分继续查找
            } else {
                left = mid + 1; // 在右半部分继续查找
            }
        }
        return -1; // 目标元素不存在
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("目标元素 " + target + " 的索引是: " + result);
        } else {
            System.out.println("目标元素 " + target + " 不存在。");
        }
    }
}

常见实践

查找第一个出现的元素

public class BinarySearchFirstOccurrence {
    public static int binarySearchFirst(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                result = mid;
                right = mid - 1; // 继续在左半部分查找，以找到第一个出现的位置
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 3, 3, 5, 7, 9};
        int target = 3;
        int result = binarySearchFirst(arr, target);
        if (result != -1) {
            System.out.println("目标元素 " + target + " 第一次出现的索引是: " + result);
        } else {
            System.out.println("目标元素 " + target + " 不存在。");
        }
    }
}

查找最后一个出现的元素

public class BinarySearchLastOccurrence {
    public static int binarySearchLast(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                result = mid;
                left = mid + 1; // 继续在右半部分查找，以找到最后一个出现的位置
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 3, 3, 5, 7, 9};
        int target = 3;
        int result = binarySearchLast(arr, target);
        if (result != -1) {
            System.out.println("目标元素 " + target + " 最后一次出现的索引是: " + result);
        } else {
            System.out.println("目标元素 " + target + " 不存在。");
        }
    }
}

最佳实践

避免整数溢出

在计算中间位置时，使用 mid = left + (right - left) / 2 而不是 mid = (left + right) / 2，可以避免整数溢出的问题。

边界条件处理

在编写二分查找代码时，要特别注意边界条件的处理，确保代码在各种情况下都能正常工作。

代码可读性和可维护性

使用有意义的变量名和注释，提高代码的可读性和可维护性。

小结

二分查找算法是一种高效的搜索算法，适用于已排序的数据集。通过不断缩小查找区间，它可以在 $O(log n)$ 的时间复杂度内找到目标元素。在 Java 中，可以使用递归或迭代的方式实现二分查找，并且可以根据具体需求进行扩展，如查找第一个或最后一个出现的元素。在实践中，要注意避免整数溢出和正确处理边界条件，以提高代码的健壮性。

参考资料

《算法导论》
Java 官方文档
GeeksforGeeks 网站