我的索引越界错误发生在哪里

Question

在编写我的第一个二进制搜索方法时遇到问题。

public static int binarySearch(int [] a, int b){
int mid = a[a.length-1]-a[0]/2;
int high = a[a.length-1];
int low = a[0];
int found = -2;
while (high > low){
for (int i = high; i >= mid; i--){
if (a[i] == b){
found = i;
}
}
for (int x = 0; x <= mid; x++){
if (a[x] == b){
found = x;
}
}
if (a[mid] < b){
low = mid;
mid = high-low/2;
} else if (a[mid] > b){
high = mid;
mid = high-low/2;
} else if (a[mid] == b){
found = mid;
}
}
return found;
}

我在runner中的call语句中出现了Index Out of Bounds错误。我已经扰乱for循环一段时间了，但我甚至不确定这是怎么回事。

Answer 1

考虑以下情况：
a=[1000200300400500]
b=200

在您的代码中，int mid = a[a.length-1]-a[0]/2;会将值分配给mid作为500-100/2 = 450。

我可以看到，在前面代码的多个位置，您使用的是a[mid]，这意味着您要求在索引450处获取a的元素。但是，您的数组只有5个元素。

基本上，当您应该处理索引时，您正在处理数组中的值。

Answer 2

您的binarySearch方法不正确。low、high和mid变量应该是数组的索引，而不是实际值。以下是它的一个简单实现

public static int binarySearch(int [] a, int b){
int mid;
int high = a.length-1;
int low = 0;
while (high > low){
mid = (low + high) / 2;
if (a[mid] > b) 
high = mid - 1;
else if (a[mid] < b) 
low = mid + 1;
else 
return mid;
}
return -2; // not found the key
}