本文旨在帮助开发者解决在使用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;
}
}代码解释
- last变量初始化： int last = array.length - 1; 将last初始化为数组最后一个元素的索引。
- 循环条件： while (first
- mid变量计算： mid = (first + last) / 2; 计算中间元素的索引。
- 比较和调整： 根据array[mid]与find的比较结果，调整first或last的值，缩小搜索范围。
注意事项
- 二分查找要求数组必须是已排序的。如果数组未排序，需要先使用Arrays.sort()方法进行排序。
- 在计算mid时，需要注意整数溢出的问题。当first和last都很大时，first + last可能会超出int的范围。为了避免溢出，可以使用mid = first + (last - first) / 2;。
- 在实际应用中，可以考虑使用Java提供的Arrays.binarySearch()方法，它已经实现了高效且稳定的二分查找算法。
总结
通过正确初始化last变量，可以避免二分查找中的数组越界异常。理解数组索引的范围是编写健壮代码的关键。在实现二分查找时，务必注意数组是否已排序，并考虑整数溢出的问题。 此外， 优先考虑使用Java标准库提供的二分查找方法，可以减少出错的可能性，并提高代码的可维护性。
