searching an unordered integer array

Question

what is the best way to search the index and the value of an integer element belonging to a big unordered integer array? which is the best searching tecnhique/algorithm for this process?

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

now say, i would like to search for the element '9' and i need to get its index of that element as well. what i mean to say is, sorting the array elements and determining it wouldnt work here(since i need to keep track of the index of the element as well). any suggestions? i am working on java by the way..

Answer 1

If you need to search (the same array) multiple times, you might create a temporary structure, which combines the original index and the value:

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

Now, list is sorted by value and then by index. We can now use binary search (for example) to look elements up. Note, though, that this is only worthwhile, if the number of times, you search for a value (now O(log n) as opposed to O(n)), dominates the time it takes to build the array ((O(n log n) due to sorting).

Alternatively, you could build an index-like structure using HashMap or TreeMap, which maps from integer value to its position in the array. In the case of using HashMap, the access time would be around O(1), in the case of the TreeMap it would be O(log n), as with the binary-search approach proposed above.

All these suggestions are clearly worthwhile only, if you have to search the array often.

Also, you should consider, that if the array is reasonably small, using a plain linear search (as suggested by others) might actually be the fastest solution due to the low "constants" involved and the good locality of the array components.

So, yet another approach could be to unpack the Pair structure again after sorting into two integer arrays (one containing the values, the other containing the indices):

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

Now you can search the values array using binary search:

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
}

Please keep in mind: the simplest solution (linear scan) might be the fastest, depending on the size of the array and the number of times you need to search for an entry. I would actually try that first, and only use one of the more complex proposals, if it turns out to be a bottle neck.