Finding range in an array

Question

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.

[Array.indexOf()](https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf) and [Array.lastIndexOf()](https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/String/lastIndexOf) are your answer, next time post code. — elreeda, Jul 05 '16 at 15:14

score 7 · Answer 1 · answered Jul 05 '16 at 15:12

7

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

answered Jul 05 '16 at 15:12

RobertoNovelo

3,347
3
21
32

1

The obvious answer – MrFabio Jul 05 '16 at 15:15

score 2 · Answer 2 · answered Jul 05 '16 at 16:32

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.

score 0 · Answer 3 · answered Jul 05 '16 at 15:28

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

score -1 · Answer 4 · answered Jul 05 '16 at 15:22

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

answered Jul 05 '16 at 15:22

Hassan

1
2

`code` var data = [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3]; var value = 1; 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); – Hassan Jul 06 '16 at 09:54

Finding range in an array

4 Answers4