9

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 ?

Improve this question
16
  • 1
    w3schools.com/jsref/jsref_slice_array.asp Commented Aug 6, 2012 at 12:00
  • 1
    @Roset: I don't have start and end index. I have values Commented Aug 6, 2012 at 12:01
  • 1
    Not from an array but you could use a more suitable data structure such as a range tree. Commented Aug 6, 2012 at 12:06
  • 1
    @Esailija, then simply use other final condition instead of equality. Commented Aug 6, 2012 at 12:18
  • 1
    @Esailija binary search can identify the smallest element larger than a given value and the largest element smaller than a given value. Do you deny that?.. Commented Aug 6, 2012 at 12:19

5 Answers 5

Reset to default
7

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;   
}
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

this could actually be slightly more efficient, but I understand Array.filter isn't available in some browsers
Notice that the middle value is outputted twice, e.g. filterBinary([0,1,2], 0, 2) == [0, 2, 1, 1]. Also, this is not a binary search, so you should rename the method :-)
3

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);
}
Improve this answer

9 Comments

The min and max are not in the array necessarily, so they would return -1. A binary search would also return -1 but faster
@Esailija: By binary search I mean a binary algorithm to return the indices of the elements that are in the range, not to search for the min/max values themselves. Still working on the code :-)
You still cannot use slice, as you have to linearly iterate the range and check all of them. If you remove that linear iteration from Qnan's answer, it won't work. So no matter how you put it, you cannot use binary search to get the indices and slice.
I can't get your latest edit to work :-P Getting empty array as result no matter what I put in. [0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 25, 243, 424].sliceRange(1,3) //[]
Oh, I can :-) The last search(es) to get upper and lower bounds do not need to be linear. Sorry for the confusion with all the edits
|
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);
}
Improve this answer

Comments

1

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/

Improve this answer

14 Comments

I see what you mean by identifying a larger value than given value and admit I wasn't thinking outside of the box enough to see that simply linearly checking the bounds given by the searches can be done to do the clean-up. I was thinking more like .slice(bs(min),bs(max)) which of course cannot be done. I am gonna float this answer above bergi's.
@Esailija thank you. Actually, it is possible to use slice() here too, but the problem is to identify exactly the bounds. The easiest way might be this: jsfiddle.net/3VR4k it might make sense to do it this way if the ranges are usually large
Yes you can use slice but it won't give correct results (So, you can't ) because the binary searches cannot identify exact bounds, but I have been wrong before... lol
Yes, the bound would have to be adjusted, but it is easy to show that the adjustment won't take up more than O(1) time, so the overall O(log(n)) is preserved: jsfiddle.net/3VR4k/4; P.S. sorry, my previous comment contained a link to the wrong fiddle.
I think, with your indizes you can use dates.slice(start+1, end); to get the correct results - low is the item before the range, and high the one after it
|
0 
  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; 
   }
Improve this answer

5 Comments

This will alter original dates array as well.
This will not work. It will remove 1 element at iCntr position
@OlegV.Volkov:- Is it fine now??
@AshwinPrabhu: tried in try it editor, and its working(w3school)
@Anonymous, no. You're doing shallow copy and by definition of question there could be many elements in original array. This considerably decrease performance.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.