时间戳

首页 > 解决方案 > 在数组中查找数字的最佳做法是什么？

java - 在数组中查找数字的最佳做法是什么？

问题描述

..还有，这里到底发生了什么？

    int [] numbers1To9 = new int[]{1,2,3,4,5,6,7,8,9};
    System.out.println("one is here, true or false?: "+Arrays.asList(numbers1To9).contains(1));

输出：一个在这里，是真是假？：假

标签： javasearch

解决方案

如果使用已排序的数组，或者当对未排序数组的排序操作被认为是“便宜的”时，这binarySearch可能是一个不错的选择；它避免了创建进一步的集合（例如Lists），因为它直接与原始数组一起工作，其机制旨在找到存储所需密钥的位置（或其中之一）。结果，您可以识别它的存在（隐式）和所在的索引。

您已经对数组进行了排序，因此在您的情况下不需要（这是使用此算法的优势）；请注意，在使用未排序Arrays.sort的数组时，必须在之前调用binarySearch以避免“未定义”结果。

例如，如果您想知道该值是否1存在：

    /*Arrays.sort(numbers1To9); -- only if unsorted*/
    boolean found = (Arrays.binarySearch((numbers1To9), 1))>=0?true:false; //--> true

例如，如果您希望获得 value 的位置2：

    /*Arrays.sort(numbers1To9); -- only if unsorted*/
    int pos = Arrays.binarySearch((numbers1To9), 2); //-->1
    boolean found = pos>=0; //--> true

binarySearch如果找不到元素，只会返回负输出。如果要找到的键是重复的，则无法保证返回指定键的哪个位置。

不管怎样，如果结果是>=0，则保证数组包含数字，并且还保证将所需的值存储在返回的索引中。

没有找到密钥时的结果有点有趣

如果找不到密钥，则显示的否定结果遵循以下逻辑：

(-(插入点) - 1)。插入点定义为将键插入数组的点：第一个元素的索引大于键，如果数组中的所有元素都小于指定的键，则为 a.length。这保证了当且仅当找到键时返回值将> = 0。

因此，如果您尝试找到任何大于 9 的数字，则插入点将为numbers1To9.length -> 9. 因此，10andINTEGER.MAX_VALUE将输出相同的位置：

int pos = Arrays.binarySearch((numbers1To9), 10);                // -(9)-1 --> pos=-10
    pos = Arrays.binarySearch((numbers1To9), Integer.MAX_VALUE); // -(9)-1 --> pos=-10

使用数字 0，插入点将是0（因为 1 更大并且它在数组中的位置是 0）：

int pos = Arrays.binarySearch((numbers1To9), 0); // -(0)-1 --> pos=-1

为了查看binarySearch对未排序数组的使用情况：

    int [] numberUnsorted= new int[]{1,2,4,9,7,6,5,8,3};
    int pos = Arrays.binarySearch((numberUnsorted), 3); //--> pos = -3  (FAIL)
        pos = Arrays.binarySearch((numberUnsorted), 9); //--> pos = -10 (FAIL)
        pos = Arrays.binarySearch((numberUnsorted), 6); //--> pos = -4  (FAIL)

所以称它们为“未定义”是一种非常仁慈的热


请注意，binarySearch 将是在数组中查找数字的“最佳实践之一”，其中数组的条件是 sorted。在数组未排序的其他情况下，您可能会意识到对其进行排序的复杂性，并决定是否需要另一种不需要排序操作的机制是更好的方法。它将取决于数组类型、大小和值。在不知道搜索的具体上下文的情况下，通常没有“最佳确定方法”

推荐阅读