时间戳

首页 > 解决方案 > 使用二分搜索在排序数组中查找元素集合？

arrays - 使用二分搜索在排序数组中查找元素集合？

问题描述

这是我要解决的挑战：

输入：

第一行包含一个整数 n，使得 1 <= n <= 10^5。
第二行包含一个由 n 个自然数组成的数组，每个不超过 10^9。数组按升序排序。
第三行包含一个整数 k，使得 1 <= k <= 10^5。
第四行包含一个由 k 个自然数组成的数组，每个不超过 10^9。

输出：

对于第二个数组中的每个数字，输出该数字在第一个数组中的索引。如果第一个数组中没有出现某个数字，则输出 -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？

标签： arraysalgorithmsearchbinary-search-treebinary-search

解决方案

该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;

推荐阅读