二分查找 (Binary Search)

算法原理

二分查找是一种在已排序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

算法步骤

1. 设定数组中的最小索引值low和最大索引值high
2. 计算中间索引值mid=(low+high)/2
3. 比较目标值target与arr[mid]的大小：
   • 若target == arr[mid]，则找到目标值，返回索引
   • 若target < arr[mid]，则在左半部分继续查找，即high = mid - 1
   • 若target > arr[mid]，则在右半部分继续查找，即low = mid + 1
4. 重复步骤2-3，直到找到目标值或low>high

代码实现

public class BinarySearch {
    // 迭代版本
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;  // 防止整数溢出
            
            if (arr[mid] == target) {
                return mid;  // 找到目标值，返回索引
            } else if (arr[mid] > target) {
                high = mid - 1;  // 在左半部分查找
            } else {
                low = mid + 1;   // 在右半部分查找
            }
        }
        
        return -1;  // 未找到目标值
    }
    
    // 递归版本
    public static int binarySearchRecursive(int[] arr, int target, int low, int high) {
        if (low > high) {
            return -1;  // 未找到目标值
        }
        
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            return binarySearchRecursive(arr, target, low, mid - 1);
        } else {
            return binarySearchRecursive(arr, target, mid + 1, high);
        }
    }

    // 测试方法
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;
        
        System.out.println("数组内容:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        
        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("找到了! 目标值 " + target + " 在索引 " + result + " 处");
        } else {
            System.out.println("未找到目标值 " + target);
        }
    }
}

应用场景

• 在有序数组中查找特定元素：这是二分查找最基本的应用场景
• 查找插入位置：可以用来确定新元素应该插入的位置以维持数组的有序性
• 数值计算：在某些数学问题中，可以用二分查找来逼近解
• 查找边界：可以用来查找满足条件的第一个或最后一个元素

优缺点