Finding a collection of elements in a sorted array using Binary Search?

Question

This is the challenge I am trying to solve:

Input:

The first line contains one integer n such that 1 <= n <= 10^5.
The second line contains an array of n natural numbers, each not exceeding 10^9. The array is sorted in ascending order.
The third line contains one integer k such that 1 <= k <= 10^5.
The fourth line contains an array of k natural numbers, each not exceeding 10^9.

Output:

For each number from the second array, output the index of this number in the first array. If some number is not presented in the first array, output -1.

In this problem, the array indexing is assumed to be started from 1.

Sample Input 1:

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

Sample Output 1:

3 1 -1 1 -1

My attempt:

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

The problem

Instead of the expected output, I got:

2
0
-6
0
-4

How can I make it return -1 for when there is no match?

Answer 1

The documentation on the binarySearch method:

Returns: index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1).

The method does not necessarily return -1 when there is no match: it could be another negative number, as you can also see when you run your code. You only know that a negative number indicates there was no match.

Secondly, you did not deal with the following specification in the task:

the array indexing is assumed to be started from 1.

So, change the following:

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

with this:

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