где происходит ошибка моего индекса за пределами границ?

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, но я даже не уверен, в чем дело.

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
}