CODEWITHSUNDEEP
javascriptarrayssorting
TheFermat
TheFermat

Reputation: 206

Finding range in an array

Lets assume we have an array of those elements (always sorted).

[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3]

Our goal is to find the min-index and max-index of a given value e.g. Lets assume we're searching for the min-index and max-index of the element 3.

We quickly see, that the min-index for 3 is 8 and the max-index is 11.

For the value 1, the min is 0 and the max is 3.

How would you develop a solution for that returns the min and max in JavaScript? I have tried to do this, but I can't figure how to, I always get the wrong answer.

Upvotes: 0

Views: 1287

Answers (4)

Rainer Zufall
Rainer Zufall

Reputation: 41

Basically Array.indexOf() and Array.lastIndexOf() will do it but they'll do a linear search (go through whole array with a loop until the element is found) which is obviously done in linear time O(n).

If it is true that your array is always sorted then we can use this property to optimize it and use binary search. It is way faster and will do it in logarithmic time O(log n).

After that we simply check the elements before (and after) the found index and until we find an element which isn't equal to our element.

For finding last occurence:

var i= foundIndex;
while(sortedArr[i] == sortedArr[foundIndex]){
    i++;
}
foundIndex = i;

And for first occurence:

var i= foundIndex;
while(sortedArr[i] == sortedArr[foundIndex]){
    i--;
}
foundIndex = i;

That's it! This will help a lot with the run time especially if you have big arrays. You can find binary search implementations everywhere, just use any of them.

Upvotes: 2

Mohammaed Abed
Mohammaed Abed

Reputation: 9

Is that what you want?

var myarr = [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3];
var minNum = myarr[0];
var maxNum = myarr[1];
var minNumStartINDX, maxNumStartINDX, minNumEndINDX, maxNumEndINDX;
/********************************************/
for (var x = 0; x < myarr.length; ++x) {
  if (minNum >= myarr[x]) {
    minNum = myarr[x];
    minNumEndINDX = x;
  }
}
for (var x = 0; x < myarr.length; ++x) {
  if (minNum >= myarr[x]) {
    minNumStartINDX = x;
    break;
  }
}
for (var x = 0; x < myarr.length; ++x) {
  if (maxNum <= myarr[x]) {
    maxNum = myarr[x];
    maxNumEndINDX = x;
  }
}
for (var x = 0; x < myarr.length; ++x) {
  if (maxNum <= myarr[x]) {
    maxNumStartINDX = x;
    break;
  }
}
/********************************************/
console.log(minNum);
console.log(minNumStartINDX + "-" + minNumEndINDX);
console.log(maxNum);
console.log(maxNumStartINDX + "-" + maxNumEndINDX);

Upvotes: 0

Hassan
Hassan

Reputation: 1

var data={1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3};
var value=3;
var min=data.length;
var max=0;

for(var key in data){
   if(data[key]==value){
      if(key<min){
           min=key;
      }
   if(key > max){
          max=key;
     }
  }
console.log(min);
console.log(max);

Upvotes: -1

RobertoNovelo
RobertoNovelo

Reputation: 3810

You can try Array.indexOf() and Array.lastIndexOf()

var sortedArr =[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3];

console.log(sortedArr.indexOf(1));
console.log(sortedArr.lastIndexOf(1));

Upvotes: 7

Related Questions