搜索属于大无序整数数组的整数元素的索引和值的最佳方法是什么？对于这个过程来说，哪个是最好的搜索技术/算法？
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);
现在，
listO(log n)O(n)(O(n log n)或者，您可以使用
HashMapTreeMapHashMapO(1)TreeMapO(log n)仅当您必须经常搜索数组时，所有这些建议显然才有价值。
此外，您应该考虑，如果数组相当小，由于涉及的“常数”较低且数组组件具有良好的局部性，因此使用简单的线性搜索（如其他人建议的）实际上可能是最快的解决方案。
因此，另一种方法可能是在排序为两个整数数组（一个包含值，另一个包含索引）后再次解压
Pairint[] 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;
}
现在您可以使用二分搜索来搜索
valuesint 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
}
请记住：最简单的解决方案（线性扫描）可能是最快的，具体取决于数组的大小和您需要搜索条目的次数。实际上，我会先尝试一下，并且只使用其中一个更复杂的建议，如果它被证明是一个瓶颈。
增强：
int[] temp = new int[]{1,4,3,6,7,8,5,2,9,......}
for (int i : temp) {
if (i == 9)
// do something
}
如果您的数组不大并且您在数组中需要的搜索时间很短，您可以将其用于线性搜索吗？
在这种情况下，在未排序的数组中，搜索操作可以通过从第一个元素到该元素想要接近它的位置的线性遍历来执行。
// Java program to implement linear
//search in unsorted array
class main {
// Function to implement
//search operation
static int findElement(int arr[] , int n , int key) {
for(int i = 0; i < n; i++ ) {
if(arr[i] == key) {
return i;
}
}
// If the element it's not found
retutn -1
}
public static void main (String args[]) {
int arr [] = {1, 4 , 3 , 6 , 7 , 8 , 5 , 2 , 9};
int n = arr.length;
int key = 9;
// Call function
int position = findElement(arr , n , key);
if(position == -1) {
System.out.println("Element not found ");
} else {
System.out.println("Element is found at index: " + (position + 1) );
}
}
}
时间复杂度：O(n) .
辅助空间：O(1) .
否则，如果您有大数组，您应该进行二分搜索并首先对数组进行排序，然后将其分成两半，然后在每一半中搜索您需要的数字。
最少的编码是：
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;
}