Найти коллекцию элементов в отсортированном массиве с помощью двоичного поиска?

Question

Это задача, которую я пытаюсь решить:

Входные данные:

Первая строка содержит одно целое число n такое, что 1 <= n <= 10 ^ 5. Во второй строке записан массив из n натуральных чисел, каждое не более 10 ^ 9. Массив отсортирован по возрастанию. В третьей строке записано одно целое число k такое, что 1 <= k <= 10 ^ 5. Четвертая строка содержит массив из k натуральных чисел, каждое из которых не превышает 10 ^ 9. </p>

Вывод:

Для каждого числа из второго массива выведите индекс этого числа в первом массиве. . Если какое-то число не представлено в первом массиве, выведите -1. ​​

В этой задаче предполагается, что индексация массива начинается с 1.

Пример ввода 1:

5
1 5 8 12 13
5
8 1 23 1 11

Пример вывода 1:

3 1 -1 1 -1

Моя попытка:

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // put your code here
        Scanner sc = new Scanner(System.in);
        int[] arrtoSearch = new int[sc.nextInt()];
        for(int i = 0;i < arrtoSearch.length;i++){
            arrtoSearch[i] = sc.nextInt();
        }
        int[] arr = new int[sc.nextInt()];
        for(int j = 0;j < arr.length;j++){
            arr[j] = sc.nextInt();
        }
        int[] newArr = new int[arr.length];
        for(int k = 0;k < arr.length;k++){
            System.out.println("arr[k]"+arr[k]);
            newArr[k] = Arrays.binarySearch(arrtoSearch, arr[k]);
        }
        for(int k = 0;k < arr.length;k++){
             System.out.println(newArr[k]);
        }
    }
}

Проблема

Вместо ожидаемого результата я получил:

2
0
-6
0
-4

Как сделать так, чтобы он возвращал -1, если совпадений нет?

Answer 1

Документация по методу binarySearch :

Возвращает: индекс ключа поиска, если он содержится в массиве внутри указанный диапазон; в противном случае (-(insertion point) - 1).

Метод не обязательно возвращает -1, если совпадения нет: это может быть другое отрицательное число, что вы также можете увидеть при запуске кода. Вы знаете только, что отрицательное число означает, что совпадения не было.

Во-вторых, вы не рассмотрели следующую спецификацию в задаче:

предполагается, что индексация массива запущена из 1.

Итак, измените следующее:

        newArr[k] = Arrays.binarySearch(arrtoSearch, arr[k]);

на это:

        int res = Arrays.binarySearch(arrtoSearch, arr[k]);
        newArr[k] = res < 0 ? -1 : res + 1;