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..

I don't think you have a choice, since you want to keep the index. Search iteratively. — Sotirios Delimanolis
– Sotirios Delimanolis, Commented Mar 13, 2013 at 15:55
can i use hashing and store the index of the element as the value? — Eashwar
– Eashwar, Commented Mar 13, 2013 at 15:57
Would it prohibitive to sort the elements as you were constructing the collection? — hertzsprung
– hertzsprung, Commented Mar 13, 2013 at 15:58
depends on what you are trying to achieve/solve. probably array is not a best data structure in your task. — Nikolay Kuznetsov
– Nikolay Kuznetsov, Commented Mar 13, 2013 at 15:58
How large is the array? Does it ever change? How frequently do you need to search? — NPE
– NPE, Commented Mar 13, 2013 at 15:59

cowls · Accepted Answer · 2013-03-13 16:39:08Z

6

If you were doing it manually you could just iterate over each array item:

public int indexOf(int search, int[] arr) {

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

    return -1;

}

If you know the array wont change in between doing many searches, you can cache the results too, using a Map.. just empty the cache whenever you change the array.

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;

}

In reality you may be better off using a Map instead of an array altogether to store this data as it is better suited to key value lookup.

edited Mar 13, 2013 at 16:39

answered Mar 13, 2013 at 15:57

cowls

24.4k9 gold badges51 silver badges78 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Eric Over a year ago

By conversion in Java, it's better to put param int[] arr before int search in the function.

Dirk · Accepted Answer · 2013-03-13 16:17:47Z

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.

thanks for the comprehensive solution, i used a hashmap to solve my problem finally!!

Jabrown207 · Accepted Answer · 2013-03-13 16:00:43Z

1

Enhanced For :

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

answered Mar 13, 2013 at 16:00

Jabrown207

2252 silver badges5 bronze badges

Comments

OldCurmudgeon · Accepted Answer · 2013-03-13 17:03:11Z

0

Begin at the beginning and go on till you come to the end: then stop.

Lewis Carroll

Unless of course you find what you are looking for before you get to the end.

edited Mar 13, 2013 at 17:03

answered Mar 13, 2013 at 15:57

OldCurmudgeon

66k18 gold badges126 silver badges220 bronze badges

Comments

Ahmed Abubaker · Accepted Answer · 2024-09-25 02:12:13Z

can you use this with linear search if your array it's not large and number that you need search time in your array it's short .

and in this case in an unsorted array , the search operation can be performed by linear traversal form the first element to the which the element want to approach it .

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

               }

         }

 }

Time Complexity: O(n) .

Auxiliary Space: O(1) .

otherwise if you have large array you should Binary Search and first sort your array and divide into tow halves and search each half for the number wich you need it .

Nikolay Kuznetsov · Accepted Answer · 2013-03-13 15:56:34Z

-1

Least coding would be:

Arrays.asList(temp).indexOf(9)

answered Mar 13, 2013 at 15:56

Nikolay Kuznetsov

9,61912 gold badges61 silver badges103 bronze badges

9 Comments

user1181445 Over a year ago

This would sweep over the list twice I believe. Just using an enhanced for loop would be the best way to do this.

Eashwar Over a year ago

is this solution similar to linear searching process?

Eashwar Over a year ago

it would sweep over the list twice? i guess then linear searching using a for loop would be better. yes.

user1181445 Over a year ago

@Eashwar Cowls' answer is the best. If you look at the source for this code you will see it iterates over the list twice, being half as efficient.

Nikolay Kuznetsov Over a year ago

@Legend, why are talking about efficiency? The OP does not specify any of his requirements.

|

1218985 · Accepted Answer · 2013-03-13 16:31:57Z

-1

Better approach is to sort the array first.

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

To scan through an unsorted array takes linear time "O(n)". You can try this if you don't want to sort the array:

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

edited Mar 13, 2013 at 16:31

answered Mar 13, 2013 at 15:59

1218985

8,1122 gold badges29 silver badges33 bronze badges

1 Comment

Nikolay Kuznetsov Over a year ago

this is a comment, not answer.

Collectives™ on Stack Overflow

searching an unordered integer array

7 Answers 7

1 Comment

1 Comment

Comments

Comments

Comments

9 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

1 Comment

1 Comment

Comments

Comments

Comments

9 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related