CODEWITHSUNDEEP
javaarraysalgorithm
Sangram Mohite
Sangram Mohite

Reputation: 754

Getting an element falling in a range from an array effeciently

In Java if I want to get the elements from an array that fall in a specific range then what would be the most efficient way to do that?

For e.g.

array 

A = [25,32,54,23,76,34];

And I want to get the 

element between 45 and 55.

That is the element:

54

So what will be the most efficient way to get it?

Upvotes: 1

Views: 210

Answers (5)

k-d
k-d

Reputation: 21

You'll have to know what elements are there in your array inorder to answer your query (element between a and b).

Incase you are going to answer about n such queries then you can probably sort the array (n log n) and then find the closest element larger than or equal to a (a being smaller than a and b) and the closest element smaller than or equal to b by using binary search (n log n + n log n) and then retrieve elements between them.

If the no.of elements between a and b is small you can probably achieve O(n log n) complexity over n queries making each query worth about O(log n) in average but if the no.of elements between a and b is of the order of n, each query will be worth O(n) complexity.

Upvotes: 0

mikera
mikera

Reputation: 106351

If you are going to search the array repeatedly, then your best option would be to sort the array and use binary search to find the low and high bounds. This will give you O(log n) performance when amortised over enough searches.

If it is a one-off search, you cannot do better than just scanning the array and comparing each element to the low/high bounds as others have suggested - this is O(n).

Upvotes: 3

D_Jones
D_Jones

Reputation: 16

I am not sure if it would be the most efficient, but I would do something like this.

    int[] rangeTracker = new int[100];
int rangeTrackIndex = 0;
For (int j = 0; j < A.getLength(); j++) {

     if ((A[j] >= 45) && (A[j] <= 55)) {
          rangeTracker[rangeTrackIndex] = A[j];
          rangeTrackIndex++;
}
}
For (int j=0; j < rangeTracker.getLength(); j++) {
     System.out.println(rangeTracker[j]);
}

Some of my syntax could be off and this could be the wrong way to do it, but I have only been working with Java for about 2 months. Furthermore I have only been working with programming for about 4 months. I hope this helps.

Upvotes: 0

Imposter
Imposter

Reputation: 2686

It takes a minimum of O(n) complexity because in-order to know how many elements are there between given ranger we have to traverse all elements at-least once since there are n elements we compute n comparisons so complexity is O(n)

coming to solution AFAIK .

n<-array.length;

for(int i=0;i<n;i++)
{
  if((a[i]<upperLimit) && (a[i]>lowerLimit))
   {
      SOP(a[i]);//or store in temp array based on your requirement
   } 
}

Upvotes: 0

Subhrajyoti Majumder
Subhrajyoti Majumder

Reputation: 41200

you can try something like this

int dLimit=45, uLimit =55, result[] = new int[A.length],j=0;
for(int i : A){
    if(i>dLimit && i<uLimit)
        result[j++] = i;
}

Upvotes: 0

Related Questions