ArrayIndexOfBoundException в двоичном поиске

Question

Я реализую двоичный поиск для двух массивов. Когда я запускаю свой код, он дает мне ошибку ArrayIndexOfBoundException: 11 строка 23, где проверяется условие if (a [m] == key). Я не совсем понимаю, что это неправильно реализовано в моем коде. Пожалуйста, помогите исправить ошибку

import java.util.Scanner; 

public class Main { 

    public static void main(String[] args) { 
     Scanner s = new Scanner(System.in); 
     int n = s.nextInt(); 
     int[] a = new int[n + 1]; 
     int i, j; 
     for (i = 0; i != a.length-1; i ++) 
      a[i] = s.nextInt(); 
     int k = s.nextInt(); 
     int[] b = new int[k+1]; 
     for (j = 0; j != b.length-1; j++) 
      b[j] = s.nextInt(); 
     int l = 0; 
     int r = a.length-1; 
     j = 0; 
     int key = b[j]; 
     int m = 0; 
     while(l <=r && j!=b.length-1){ 
      m = (l+r)/2; 
      if (a[m] == key){ 
       System.out.println(m+1); 
       j++; 
       if (j != b.length-1) 
       key = b[j]; 

      } 
      else if (a[m] > key) r = m -1; 
      else if (a[m] < key) l = m + 1; 
      if (l > r){ 
       System.out.println("-1"); 
       j++; 
       if (j != b.length-1) 
       key = b[j]; 
       l = 0; 
       r = a.length-1; 

      } 
     } 
    } 

}

Answer 1

Массивы в Java имеют индексы, начиная с 0 и заканчивая (arrayLength - 1). Таким образом, когда вы дойдете до конца цикла while, с l == r == a.length, (l+r)/2 также равно a.length. Поскольку a.length является одним большим, чем максимальный индекс в массиве, он выходит за рамки и исключение.

Answer 2

Я не знаю, почему вы используете два массива для двоичного поиска, но причиной вашего ArrayIndexOutOfBoundsException является то, что в java массивы основаны на нулевом значении, это означает, что первым элементом является элемент в позиции 0, второй в положении 1 и т. д., до последнего, который находится в положении array.length - 1. В вашем коде вы инициализируете l=1; r=a.length, и в этом проблема. Представьте себе массив с одним элементом. Он будет находиться в позиции 0 (не 1). Затем вы сделаете m=(l+r)/2 (тогда m будет 1), и вы проверите значение a[1], которое является неправильным, потому что единственным элементом в вашем массиве является a[0].

Answer 3

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    Scanner s = new Scanner(System.in); 
    int n = s.nextInt(); 
    int[] a = new int[n + 1]; 
    int i, j; 
    for (i = 0; i < a.length; i++) 
     a[i] = s.nextInt(); 
    int k = s.nextInt(); 
    int[] b = new int[k + 1]; 
    for (j = 0; j < b.length; j++) 
     b[j] = s.nextInt(); 
    int l = 0; 
    int r = a.length - 1; 
    j = 0; 
    int key = b[j]; 
    int m = 0; 
    while (l <= r && j != b.length) { 
     m = (l + r)/2; 
     System.out.println("left " + l + " right " + r); 
     if (a[m] == key) { 
      System.out.println(m); 
      j++; 
      if (j != b.length) 
       key = b[j]; 

     } else if (a[m] > key) 
      r = m - 1; 
     else if (a[m] < key) 
      l = m + 1; 
     if (l > r) { 
      System.out.println("-1"); 
      j++; 
      if (j != b.length) 
       key = b[j]; 
      l = 1; 
      r = a.length; 

     } 
    } 
} 

как указано выше. Вы должны иметь в виду, что массивы начинаются с 0 (NOT 1), пока arrayName.length() - 1. Надеюсь это поможет.