Java 二分搜索

二分搜索（Binary Search）是一种高效的搜索算法，用于在有序数组中查找特定元素。它的基本思想是通过将搜索区间分成两半，逐步缩小搜索范围，从而快速找到目标元素。

以下是二分搜索的Java实现：

public class BinarySearch {  
  
    // 递归实现二分搜索  
    public static int binarySearchRecursive(int[] array, int target) {  
        return binarySearchRecursive(array, target, 0, array.length - 1);  
    }  
  
    private static int binarySearchRecursive(int[] array, int target, int left, int right) {  
        if (left > right) {  
            return -1; // 未找到目标元素  
        }  
  
        int mid = left + (right - left) / 2; // 防止(left + right) / 2可能导致的溢出  
  
        if (array[mid] == target) {  
            return mid; // 找到目标元素，返回索引  
        } else if (array[mid] < target) {  
            return binarySearchRecursive(array, target, mid + 1, right); // 在右半部分继续搜索  
        } else {  
            return binarySearchRecursive(array, target, left, mid - 1); // 在左半部分继续搜索  
        }  
    }  
  
    // 迭代实现二分搜索  
    public static int binarySearchIterative(int[] array, int target) {  
        int left = 0;  
        int right = array.length - 1;  
  
        while (left <= right) {  
            int mid = left + (right - left) / 2;  
  
            if (array[mid] == target) {  
                return mid; // 找到目标元素，返回索引  
            } else if (array[mid] < target) {  
                left = mid + 1; // 在右半部分继续搜索  
            } else {  
                right = 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 resultRecursive = binarySearchRecursive(array, target);  
        int resultIterative = binarySearchIterative(array, target);  
  
        System.out.println("Recursive search result: " + resultRecursive);  
        System.out.println("Iterative search result: " + resultIterative);  
    }  
}

代码解释

1. 递归实现：
   • binarySearchRecursive(int[] array, int target) 是对外公开的递归方法，它调用了一个带有额外参数 left 和 right 的私有递归方法。
   • 私有递归方法 binarySearchRecursive(int[] array, int target, int left, int right) 实现了实际的二分搜索逻辑。
   • 如果 left 大于 right，表示搜索区间为空，返回 -1 表示未找到目标元素。
   • 计算中间索引 mid，并比较 array[mid] 与 target。
   • 根据比较结果，递归地在左半部分或右半部分继续搜索。
2. 迭代实现：
   • binarySearchIterative(int[] array, int target) 方法使用 while 循环实现二分搜索。
   • 初始化 left 和 right 指针，分别指向数组的起始和结束位置。
   • 在循环中计算中间索引 mid，并比较 array[mid] 与 target。
   • 根据比较结果，更新 left 或 right 指针，缩小搜索范围。
   • 如果循环结束仍未找到目标元素，返回 -1。

注意事项

• 二分搜索要求数组必须是有序的。
• 递归实现和迭代实现的时间复杂度均为 O(log n)，其中 n 是数组的长度。
• 递归实现可能会因为栈深度过大而导致栈溢出，对于非常大的数组，建议使用迭代实现。

希望这个解释和代码示例能帮助你理解Java中的二分搜索算法！