当前位置：首页 > article >正文

二分查找--快速地将搜索空间减半

article 2024/11/16 3:17:32

二分查找是一种在有序数组中查找特定元素的高效算法。其基本思想是将目标值与数组中间元素进行比较，如果目标值与中间元素相等，则查找成功；如果目标值小于中间元素，则在数组的左半部分继续查找；如果目标值大于中间元素，则在数组的右半部分继续查找。这个过程会不断重复，直到找到目标值或者搜索范围为空。

递归实现：

public class BinarySearch {
    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; // 找到目标值，返回索引
            }
            
            // 如果目标值小于中间元素，则在左半部分继续查找
            if (target < arr[mid]) {
                right = mid - 1;
            } else {
                // 如果目标值大于中间元素，则在右半部分继续查找
                left = mid + 1;
            }
        }
        
        // 如果没有找到目标值，返回-1
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {-3, 10, 11, 21, 34, 54, 60, 78};
        int target = 21;
        
        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("元素位于数组的索引：" + result);
        } else {
            System.out.println("数组中没有找到元素。");
        }
    }
}

在这个例子中，binarySearch方法接受一个整型数组arr和一个要查找的target值。如果找到了target值，方法将返回它在数组中的索引；如果没有找到，则返回-1。

请注意，二分查找算法要求数组是有序的。如果数组是无序的，那么在执行二分查找之前需要先对数组进行排序。

非递归实现：

public class BinarySearch {
    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; // 找到目标值，返回索引
            }
            
            // 如果目标值小于中间元素，则在左半部分继续查找
            if (target < arr[mid]) {
                right = mid - 1;
            } else {
                // 如果目标值大于中间元素，则在右半部分继续查找
                left = mid + 1;
            }
        }
        
        // 如果没有找到目标值，返回-1
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {-3, 10, 11, 21, 34, 54, 60, 78};
        int target = 21;
        
        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("元素位于数组的索引：" + result);
        } else {
            System.out.println("数组中没有找到元素。");
        }
    }
}

这段代码与我之前提供的递归版本在逻辑上是相同的，但是它使用了一个while循环来代替递归调用。循环会一直执行，直到left大于right，这意味着查找范围已经为空，无法再继续查找。在每次迭代中，算法都会更新left和right的值，将查找范围缩小一半。

这种非递归的方法在某些情况下可能更受青睐，因为它避免了递归可能带来的栈溢出问题，尤其是在处理大规模数据时。此外，非递归版本通常在调试时也更容易跟踪。

在实际的工程实践中，二分查找是一种非常高效的算法，它被广泛应用于多种场景中，尤其是在需要快速查找和排序的情况下。以下是一些常见的使用二分查找解决的问题：

查找有序数组中的元素：