Values between range in javascript array

Question

I have an array sorted in ascending order in java script which contains dates in milliseconds.

// Sample data; This may grow upto 1k or 2k
var dates = [1333391400000,1335292200000,1335810600000,1336329000000,1336933800000,1337020200000,
1337193000000,1337538600000,1337625000000,1337797800000,1338316200000,1338921000000,
1339093800000,1339439400000,1340303400000,1341772200000,1342463400000,1343068200000];

I don't have start and end index. I have values. I need to get all dates between 2 dates (Min and Max) from the java script array. I am getting this array from Java through JSON.

Here is the method to get dates between min and max:

function getDatesBetweenRange(min,max){
    var subArray = [];
    var value, jCntr=0;
    for(var iCntr=0;iCntr<dates.length;iCntr++){
         value = dates[iCntr];
         if(value>max)
             break;
         if(value >=min && value <=max){
             subArray[jCntr++]= value;
         }
    }
    return subArray;
}

As array is in ascending sorted order; I am breaking loop if I get max value than the provided max value in the argument.

Is there any other efficient way to get values from Java Script array ?

Answer 1

You might use binary search to get the indizes, then use slice:

Array.prototype.sliceRange = function(min, max) {
    if (min > max) return this.sliceRange(max, min);
    var l = 0,
        r = this.length;
    // find an element at index m that is in range
    rough: {
        while (l < r) {
            var m = Math.floor(l + (r - l) / 2);
            if (this[m] < min)
                l = m + 1;
            else if (this[m] > max)
                r = m;
            else
                break rough;
        }
        // l == r: none was found
        return [];
    }
    var lr = m, // right boundary for left search
        rl = m; // left boundary for right search
    // get first position of items in range (l == lr)
    while (l < lr) {
        m = Math.floor(l + (lr - l) / 2);
        if (this[m] < min)
            l = m + 1;
        else
            lr = m;
    }
    // get last position of items in range (r == rl)
    while (rl < r) {
        m = Math.floor(rl + (r - rl) / 2);
        if (this[m] > max)
            r = m;
        else
            rl = m + 1;
    }
    // return the items in range
    return this.slice(l, r);
}

(Demo)

---

Yet, @Qnan's approach to do only one and a half searches (instead of my three half searches) is more straightforward and should not suffer any disadvantages. I only would use loops that result in exact indices:

Array.prototype.sliceRange = function(min, max) {
    if (min > max) return this.sliceRange(max, min);
    var l = 0,
        c = this.length,
        r = c;
    // get first position of items in range (l == c)
    while (l < c) {
        var m = Math.floor(l + (c - l) / 2);
        if (this[m] < min)
            l = m + 1;
        else
            c = m;
    }
    // get last position of items in range (c == r)
    while (c < r) {
        var m = Math.floor(c + (r - c) / 2);
        if (this[m] > max)
            r = m;
        else
            c = m + 1;
    }
    // return the items in range
    return this.slice(l, r);
}

Answer 2

The problem with trying to optimize the loop like this (breaking out of the sorted list after max is reached) is that you are doing a check each time you iterate. Its faster in some cases to just iterate through the entire list. Particularly when the values you are searching for are at the end of the list (e.g. more recent dates)

But, if it makes a difference you need a binary search algorithm. Lodash has a function that uses a binary search to retrieve the index where a value would be inserted. Combine this with slice and the result should be optimal.

Using [Lodash][1]

// sliced :  get all values between+including min-max from sorted array of numbers
// @param array sorted timestamps
// @param min timestamp minimum
// @param max timestamp maximum
function sliced(array,min,max){
    return array.slice(_.sortedIndex(array, min),_.sortedIndex(array, max)+1);
}

Answer 3

Here's a semi binary filter method that seems more efficient (at least in my browsers - Chrome, Firefox, IE9)

function filterBinary(arr,min,max){
 var len   = arr.length
    ,up    = -1
    ,down  = len
    ,rrange= []
    ,mid   = Math.floor(len/2) 
 ;
 while (up++<mid && down-->mid){
    if (arr[up]>=max || arr[down]<=min){break;}
    if (arr[up]>=min){
      rrange.push(arr[up]);
    }
    if (arr[down]<=max){
      rrange.push(arr[down]);
    }
 }
 return rrange;   
}

Answer 4

Here's roughly what the binary search would look like in this case

var dates = [1333391400000,1335292200000,1335810600000,1336329000000,1336933800000,1337020200000,
1337193000000,1337538600000,1337625000000,1337797800000,1338316200000,1338921000000,
1339093800000,1339439400000,1340303400000,1341772200000,1342463400000,1343068200000];

function getDatesBetweenRange(min, max) {
    var subArray = [];
    var value, iCntr;
    var start, end;

    var low = 0, high = dates.length - 1;
    while (high - low > 1) {
        centre = Math.floor((high + low) / 2);
        if (dates[centre] < min)
            low = centre;
        else 
            high = centre;
    }
    start = low;
    high = dates.length - 1
    while (high - low > 1) {
        centre = Math.floor((high + low) / 2);
        if (dates[centre] > max)
            high = centre;
        else 
            low = centre;
    }
    end = high;

    for (var i = start; i < end; i++) {
        value = dates[i];
        if (value < min) {
            continue;
        }
        if (value > max) {
            break;
        }
        subArray.push(value);
    }
    return subArray;
}

console.log(getDatesBetweenRange(1337193000000, 1337797800000));​

This follows the code by @Stano, except that binary search is ran twice to identify the tighter bounds. It can be improved, of course.

Here's the fiddle http://jsfiddle.net/EJsmy/1/

Answer 5

  function getDatesBetweenRange(min,max)
    {   
      var subArray = dates.slice(0,dates.length-1);

      for(var iCntr=0;iCntr<dates.length;iCntr++)
       {
       if(!(dates[iCntr] >=min && dates[iCntr] <=max))
          {
             subArray.splice(iCntr,1); 
          }
        }
       return subArray; 
   }