使用二进制搜索查找排序数组中的元素集合？

Question

这是我要解决的挑战：

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

我的尝试：

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

问题

我得到的不是预期的输出：

如果没有匹配项，我怎样才能使 return -1？

Answer 1

关于 binarySearch method 的文档：

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

当没有匹配项时，该方法不一定 return -1：它可能是另一个负数，正如您在运行您的代码时也可以看到的那样。你只知道负数表示没有匹配。

其次，您在任务中没有处理以下规范：

the array indexing is assumed to be started from 1.

因此，更改以下内容：

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

有了这个：

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

使用二进制搜索查找排序数组中的元素集合？

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

arrays

algorithm

search

binary-search

binary-search-tree

Input:

Output:

Sample Input 1:

Sample Output 1:

我的尝试：

问题