Efficient way to search within unsorted array
I have an unsorted array A containing value within range 0 to 100. I have multiple query of format QUERY(starting array index, ending array index, startValue, endValue). I want to return array of indexes whose value lies within startValue and endValue. Naive approach is taking O(n) time for each query and i needed efficient algorithm. Also, query are not known initially.
As Helios says, there's no way round this. If the array is unsorted, you have to examine every element.
You could use threads to examine different parts of the array at the same time and in doing so get an improvement if the hardware can handle it. For small arrays, the extra overhead of threading could cause it to actually take longer, though.
Since you have multiple queries, sorting it first would then give you fast queries.
You could use threads to examine different parts of the array at the same time and in doing so get an improvement if the hardware can handle it. For small arrays, the extra overhead of threading could cause it to actually take longer, though.
Since you have multiple queries, sorting it first would then give you fast queries.
Set up a
vector< vector<int> > bucket( 101 );
Pass once through the array, pushing-back the indices into the appropriate vector elements of bucket.
It will be an O(N) operation for one query ... but multiple queries should take less time, since you only need to consider between bucket[startValue] and bucket[endValue] and those vectors will contain the indices in order.
vector< vector<int> > bucket( 101 );
Pass once through the array, pushing-back the indices into the appropriate vector elements of bucket.
It will be an O(N) operation for one query ... but multiple queries should take less time, since you only need to consider between bucket[startValue] and bucket[endValue] and those vectors will contain the indices in order.
Topic archived. No new replies allowed.