修复二分查找中的数组越界异常

本文旨在帮助开发者解决在使用Java实现二分查找算法时遇到的数组越界异常。通过分析错误代码，明确数组索引的正确范围，并提供修正后的代码示例，确保二分查找算法的稳定运行，避免ArrayIndexOutOfBoundsException。

二分查找是一种高效的搜索算法，适用于已排序的数组。然而，在实现过程中，稍有不慎就可能出现数组越界异常（ArrayIndexOutOfBoundsException）。本文将分析一个典型的二分查找错误案例，并提供正确的实现方式。

问题分析

导致ArrayIndexOutOfBoundsException的根本原因是访问了数组中不存在的索引。在Java中，数组的索引从0开始，到array.length - 1结束。如果尝试访问array[array.length]，就会抛出该异常。

在提供的代码中，错误出现在binarySearch方法中，last变量的初始化方式不正确：

int last = array.length; // 错误：last应该指向数组的最后一个元素的索引

这导致在后续的循环中，mid的计算结果可能超出数组的有效索引范围，从而引发异常。

解决方案

要修复这个问题，需要将last变量初始化为array.length - 1，指向数组的最后一个元素的索引。

import java.lang.Math;
import java.util.Arrays;
import java.util.Random;

class Search {
    public static void main(String[] args) {
        double[] array = new double[9999];
        for (int i = 0; i < array.length; i++) {
            array[i] = (double) (Math.random() * 9999);
        }
        Arrays.sort(array);
        System.out.println(binarySearch(array, new Random().nextDouble(9999)));
    }

    public static int binarySearch(double[] array, double find) {
        int first = 0;
        int last = array.length - 1; // Corrected: last now points to the last element's index
        int mid;

        while (first <= last) {
            mid = (first + last) / 2;

            if (array[mid] < find) {
                first = mid + 1;
            } else if (array[mid] == find) {
                return mid;
            } else {
                last = mid - 1;
            }
        }
        return -1;
    }
}

代码解释

1. last变量初始化： int last = array.length - 1; 将last初始化为数组最后一个元素的索引。
2. 循环条件： while (first
3. mid变量计算： mid = (first + last) / 2; 计算中间元素的索引。
4. 比较和调整： 根据array[mid]与find的比较结果，调整first或last的值，缩小搜索范围。

注意事项

• 二分查找要求数组必须是已排序的。如果数组未排序，需要先使用Arrays.sort()方法进行排序。
• 在计算mid时，需要注意整数溢出的问题。当first和last都很大时，first + last可能会超出int的范围。为了避免溢出，可以使用mid = first + (last - first) / 2;。
• 在实际应用中，可以考虑使用Java提供的Arrays.binarySearch()方法，它已经实现了高效且稳定的二分查找算法。

总结

通过正确初始化last变量，可以避免二分查找中的数组越界异常。理解数组索引的范围是编写健壮代码的关键。在实现二分查找时，务必注意数组是否已排序，并考虑整数溢出的问题。 此外， 优先考虑使用Java标准库提供的二分查找方法，可以减少出错的可能性，并提高代码的可维护性。

以上就是修复二分查找中的数组越界异常的详细内容，更多请关注php中文网其它相关文章！