Binary Search 原理在 Java 中如何体现

二分查找（Binary Search）是一种高效的查找算法，它的基本原理是在有序数组中通过不断缩小查找范围来快速定位目标元素。在Java中，二分查找可以通过迭代或递归的方式实现。以下是二分查找的原理以及在Java中的体现：

原理

1. 初始范围：设定查找范围的起始索引low和结束索引high，通常初始时low为0，high为数组长度减1。
2. 计算中间索引：计算中间索引mid，通常使用(low + high) / 2或low + (high - low) / 2来避免整数溢出。
3. 比较中间元素：将目标值与中间索引处的元素进行比较：
   • 如果目标值等于中间元素，则查找成功，返回中间索引。
   • 如果目标值小于中间元素，则在左半部分继续查找，更新high为mid - 1。
   • 如果目标值大于中间元素，则在右半部分继续查找，更新low为mid + 1。
4. 重复步骤2和3，直到low超过high，表示查找范围为空，查找失败，返回-1或其他表示未找到的值。

Java实现

以下是二分查找的迭代实现和递归实现：

迭代实现

public class BinarySearch {
    public static int binarySearch(int[] array, int target) {
        int low = 0;
        int high = array.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // 避免整数溢出
            if (array[mid] == target) {
                return mid; // 找到目标值，返回索引
            } else if (array[mid] < target) {
                low = mid + 1; // 在右半部分继续查找
            } else {
                high = mid - 1; // 在左半部分继续查找
            }
        }

        return -1; // 未找到目标值
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 7;
        int result = binarySearch(array, target);
        System.out.println("Target found at index: " + result);
    }
}

递归实现

public class BinarySearchRecursive {
    public static int binarySearch(int[] array, int target, int low, int high) {
        if (low > high) {
            return -1; // 未找到目标值
        }

        int mid = low + (high - low) / 2; // 避免整数溢出
        if (array[mid] == target) {
            return mid; // 找到目标值，返回索引
        } else if (array[mid] < target) {
            return binarySearch(array, target, mid + 1, high); // 在右半部分继续查找
        } else {
            return binarySearch(array, target, low, mid - 1); // 在左半部分继续查找
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 7;
        int result = binarySearch(array, target, 0, array.length - 1);
        System.out.println("Target found at index: " + result);
    }
}

注意事项

• 二分查找要求数组是有序的。
• 在计算中间索引时，使用low + (high - low) / 2可以避免整数溢出的问题。
• 递归实现需要注意栈溢出的问题，特别是对于非常大的数组。

通过上述代码和解释，可以看到二分查找在Java中的实现非常直观和高效。