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

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;
  }

我在运行器中的调用语句处得到了一个Index Out of Bounds错误。我已经在for-loops上搞了一段时间，但我甚至不确定这就是问题所在。

Answer 1

考虑这样的情况：a=[100，200，300，400，500] b=200

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

我可以看到，在你前面的代码中，有多处使用了 a[mid] 这意味着你要求获取的是 a 在索引450处。然而，你的数组只有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
}