What is the fast way of getting an index of an element in an array ?

Question

I was asked this question in an interview. Although the interview was for dot net position, he asked me this question in context to java, because I had mentioned java also in my resume.

How to find the index of an element having value X in an array ?

I said iterating from the first element till last and checking whether the value is X would give the result. He asked about a method involving less number of iterations, I said using binary search but that is only possible for sorted array. I tried saying using IndexOf function in the Array class. But nothing from my side answered that question.

Is there any fast way of getting the index of an element having value X in an array ?

Answer 1

As long as there is no knowledge about the array (is it sorted? ascending or descending? etc etc), there is no way of finding an element without inspecting each one.

Also, that is exactly what indexOf does (when using lists).

Answer 2

Puneet - in .net its:

string[] testArray = {"fred", "bill"};
var indexOffset = Array.IndexOf(testArray, "fred");

[edit] - having read the question properly now, :) an alternative in linq would be:

string[] testArray = { "cat", "dog", "banana", "orange" };
int firstItem = testArray.Select((item, index) => new
{
    ItemName = item,
    Position = index

}).Where(i => i.ItemName == "banana")
  .First()
  .Position;

this of course would find the FIRST occurence of the string. subsequent duplicates would require additional logic. but then so would a looped approach.

jim

Answer 3

If a binary search isn't possible (beacuse the array isn't sorted) and you don't have some kind of advanced search index, the only way I could think of that isn't O(n) is if the item's position in the array is a function of the item itself (like, if the array is [10, 20, 30, 40], the position of an element n is (n / 10) - 1).

Answer 4

It's a question about data structures and algorithms (altough a very simple data structure). It goes beyond the language you are using.

If the array is ordered you can get O(log n) using binary search and a modified version of it for border cases (not using always (a+b)/2 as the pivot point, but it's a pretty sophisticated quirk).

If the array is not ordered then... good luck.

He can be asking you about what methods you have in order to find an item in Java. But anyway they're not faster. They can be olny simpler to use (than a for-each - compare - return).

There's another solution that's creating an auxiliary structure to do a faster search (like a hashmap) but, OF COURSE, it's more expensive to create it and use it once than to do a simple linear search.

Answer 5

Take a perfectly unsorted array, just a list of numbers in memory. All the machine can do is look at individual numbers in memory, and check if they are the right number. This is the "password cracker problem". There is no faster way than to search from the beginning until the correct value is hit.

Answer 6

Are you sure about the question? I have got a questions somewhat similar to your question.

Given a sorted array, there is one element "x" whose value is same as its index find the index of that element.

For example: //0,1,2,3,4,5,6,7,8,9,10
int a[10]={1,3,5,5,6,6,6,8,9,10,11};

at index 6 that value and index are same.

for this array a, answer should be 6.

This is not an answer, in case there was something missed in the original question this would clarify that.

Answer 7

A practical way of finding it faster is by parallel processing.

Just divide the array in N parts and assign every part to a thread that iterates through the elements of its part until value is found. N should preferably be the processor's number of cores.

Answer 8

How to find the index of an element having value X in an array ?

This would be fast:

int getXIndex(int x){
    myArray[0] = x;
    return 0;
}

Answer 9

Maybe he wants to test your knowledge about Java.

There is Utility Class called Arrays, this class contains various methods for manipulating arrays (such as sorting and searching)

http://download.oracle.com/javase/6/docs/api/java/util/Arrays.html

In 2 lines you can have a O(n * log n) result:

    Arrays.sort(list); //O(n * log n)
    Arrays.binarySearch(list, 88)); //O(log n)

Answer 10

Use a quantum computer:

http://en.wikipedia.org/wiki/Grover%27s_algorithm