跳转至

Java 二分查找代码详解

简介

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。相比于顺序查找需要遍历整个数组，二分查找每次迭代都能将搜索区间减半，大大提高了查找效率。在 Java 中，实现二分查找的代码有多种方式，本文将深入探讨其基础概念、使用方法、常见实践以及最佳实践。

目录

  1. 基础概念
  2. 使用方法
  3. 常见实践
  4. 最佳实践
  5. 小结
  6. 参考资料

基础概念

二分查找的核心思想是利用数组的有序性，通过将目标值与数组中间元素进行比较，逐步缩小搜索范围。如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。这个过程不断重复，直到找到目标值或搜索区间为空。

使用方法

递归实现

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int target, int left, int right) {
        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, target, left, mid - 1);
        } else {
            return binarySearch(arr, target, mid + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int result = binarySearch(arr, target, 0, arr.length - 1);
        if (result == -1) {
            System.out.println("目标元素未找到");
        } else {
            System.out.println("目标元素在索引 " + result + " 处");
        }
    }
}

迭代实现

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};
        int target = 7;
        int result = binarySearch(arr, target);
        if (result == -1) {
            System.out.println("目标元素未找到");
        } else {
            System.out.println("目标元素在索引 " + result + " 处");
        }
    }
}

常见实践

查找第一个和最后一个出现的位置

有时候我们不仅需要找到目标元素，还需要知道它在数组中第一次和最后一次出现的位置。

public class BinarySearchFirstAndLast {
    public static int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        result[0] = findFirst(nums, target);
        result[1] = findLast(nums, target);
        return result;
    }

    private static int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (mid == 0 || nums[mid - 1] != target) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    private static int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (mid == nums.length - 1 || nums[mid + 1] != target) {
                    return mid;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] result = searchRange(nums, target);
        System.out.println("第一个位置: " + result[0]);
        System.out.println("最后一个位置: " + result[1]);
    }
}

最佳实践

  1. 确保数组有序：二分查找的前提是数组必须有序。在进行二分查找之前，务必对数组进行排序。
  2. 处理边界情况：在代码中要仔细处理边界情况，如数组为空、目标值不存在等。
  3. 选择合适的实现方式：递归实现简洁但可能存在栈溢出问题，适用于较小规模的数组；迭代实现更高效，适用于大规模数组。
  4. 优化性能：在计算中间索引时，使用 left + (right - left) / 2 而不是 (left + right) / 2，可以避免 left + right 可能导致的整数溢出。

小结

本文详细介绍了 Java 中二分查找的基础概念、使用方法、常见实践以及最佳实践。通过递归和迭代两种方式实现了基本的二分查找，并展示了如何查找目标元素的第一个和最后一个出现位置。在实际应用中，应根据具体情况选择合适的实现方式，并注意处理边界情况和优化性能，以充分发挥二分查找的优势。

参考资料

  1. 《Effective Java》
  2. Oracle Java 官方文档
  3. LeetCode 相关题目及讨论区