Java 二分查找代码解析

简介

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。它通过不断将搜索区间缩小一半，大大减少了查找所需的时间复杂度，从线性时间（如普通的顺序查找）降低到对数时间。在 Java 中，实现二分查找代码能够让我们更高效地处理数据检索任务。本文将深入探讨 Java 二分查找代码的基础概念、使用方法、常见实践以及最佳实践。

目录

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

基础概念

二分查找的核心思想基于分治策略。假设有一个有序数组，要查找的目标元素为 target。算法首先确定数组的中间位置 mid，然后将中间元素 arr[mid] 与目标元素 target 进行比较： - 如果 arr[mid] 等于 target，则找到目标元素，返回 mid。 - 如果 arr[mid] 大于 target，说明目标元素在数组的左半部分，继续在左半部分数组中查找。 - 如果 arr[mid] 小于 target，说明目标元素在数组的右半部分，继续在右半部分数组中查找。

不断重复上述过程，直到找到目标元素或者搜索区间为空。

使用方法

递归实现

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);
        if (result[0] != -1) {
            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]);
    }
}

查找最接近的元素

在一些场景中，我们需要找到数组中最接近目标值的元素。

public class BinarySearchClosest {
    public static int findClosest(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left < right - 1) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (Math.abs(arr[left] - target) <= Math.abs(arr[right] - target)) {
            return left;
        } else {
            return right;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 7, 10, 15};
        int target = 6;
        int result = findClosest(arr, target);
        System.out.println("最接近目标值的元素索引: " + result);
    }
}

最佳实践

• 确保数组有序：二分查找的前提是数组必须有序。在进行二分查找之前，务必先对数组进行排序。可以使用 Java 自带的 Arrays.sort() 方法。
• 避免溢出：在计算中间位置 mid 时，使用 left + (right - left) / 2 而不是 (left + right) / 2，以防止 left + right 可能导致的整数溢出。
• 考虑边界情况：仔细处理数组为空、目标元素不存在等边界情况，确保代码的健壮性。

小结

本文详细介绍了 Java 二分查找代码的基础概念、使用方法（递归和迭代）、常见实践（查找第一个和最后一个位置、查找最接近元素）以及最佳实践。二分查找是一种高效的查找算法，在处理有序数组的查找任务时能够显著提高性能。掌握这些知识和技巧，能够帮助开发者在实际项目中更高效地实现数据检索功能。

参考资料

• 《Effective Java》
• Oracle Java 官方文档
• 各大在线编程学习平台相关教程