搜索无序整数数组

搜索属于大型无序整数数组的整数元素的索引和值的最佳方法是什么?这个过程的最佳搜索技术/算法是什么?

int[] temp = new int[]{1,4,3,6,7,8,5,2,9,......}

现在说，我想搜索元素'9'，我也需要得到该元素的索引。我的意思是，对数组元素进行排序并确定它在这里不起作用(因为我还需要跟踪元素的索引)。有什么建议吗?顺便说一下，我正在研究Java .

如果你是手动操作，你可以只迭代每个数组项:

public int indexOf(int search, int[] arr) {
    for(int i = 0; i < arr.length; i++) {
        if(arr[i] == search) {
            return i;
        }
    }
    return -1;
}

如果你知道数组不会在多次搜索之间改变，你也可以缓存结果，使用Map..只要在更改数组时清空缓存即可。

private Map<Integer, Integer> indexCache;
public int indexOf(int search, int[] arr) {
    Integer cachedIndex = indexCache.get(search);
    if(cachedIndex != null) return cachedIndex;
    for(int i = 0; i < arr.length; i++) {
        if(arr[i] == search) {
            indexCache.put(search, i);
            return i;
        }
    }
    return -1;
}

实际上，最好使用Map而不是数组来存储这些数据，因为它更适合键值查找。

如果您需要多次搜索(同一个数组)，您可以创建一个临时结构，它将原始索引和值组合在一起:

class Pair implements Comparable<Pair> {
    final int index;
    final int value;
    Pair(int index, int value) {
        this.index = index;
        this.value = value;
    }
    public int compareTo(Pair oth) {
        if (value < oth.value) return -1;
        else if (value > oth.value) return 1;
        else if (index < oth.index) return -1;
        else if (index > oth.index) return 1;
        else return 0;
    }
}
final ArrayList<Pair> list = new ArrayList<Pair>();
for (int k = 0; k < array.length; ++k) {
    list.add(new Pair(k, array[k]);
}
Arrays.sort(list);

现在，list先按值排序，再按索引排序。我们现在可以使用二分查找(例如)来查找元素。但是，请注意，只有在搜索值的次数(现在是O(log n)而不是O(n))超过构建数组所需的时间((O(n log n)由于排序)时，才值得这样做。

或者，您可以使用HashMap或TreeMap构建一个类似索引的结构，它将整数值映射到它在数组中的位置。在使用HashMap的情况下，访问时间将在O(1)左右，在TreeMap的情况下，访问时间将在O(log n)左右，就像上面提出的二进制搜索方法一样。

所有这些建议显然都是值得的，如果你必须经常搜索数组。

此外，您应该考虑，如果数组相当小，使用普通的线性搜索(如其他人所建议的)实际上可能是最快的解决方案，因为所涉及的"常数"很少，数组组件的位置也很好。

因此，另一种方法可能是在将Pair结构体排序为两个整数数组(一个包含值，另一个包含索引)之后再次解包:

int[] values = new int[list.size()];
int[] indices = new int[list.size()];
int pt = 0;
for (Pair p: list) {
    values[pt] = p.value;
    indices[pt] = p.index;
    pt += 1;
}

现在您可以使用二进制搜索来搜索values数组:

int position = Arrays.binarySearch(values, valueToLookFor);
if (position >= 0) {
    // Found it!
    int index = indices[position];
    System.out.println("Value was originally stored in " + index);
} else {
    // Value not found
}

请记住:最简单的解决方案(线性扫描)可能是最快的，这取决于数组的大小和您需要搜索条目的次数。我实际上会先尝试一下，并且只使用一个更复杂的建议，如果它被证明是一个瓶颈。

增强For:

  int[] temp = new int[]{1,4,3,6,7,8,5,2,9,......}
    for (int i : temp) {
      if (i == 9)
        // do something
    }

从开头开始，一直到结尾，然后停下来。

刘易斯·卡罗尔的那首

除非你在读完之前找到了你想要的

最少的编码是:

Arrays.asList(temp).indexOf(9)

更好的方法是先对数组进行排序。

Arrays.sort(array);
Arrays.binarySearch(array, value);

扫描一个无序数组需要线性时间"O(n)"。如果您不想对数组进行排序，可以尝试这样做:

public int find(int[] array, int value) {
        int index = -1;
        for (int i=0; i<array.length; i++) {
            if(array[i] == value) { index = i; }
        }
        return index;            
    }

相关内容

最新更新

热门标签：