Logic for checking in-between two numbers

Question

I would like to determine where the zone is given an arbitrary number.

zones = [0, 150, 300, 400, 600, 800]

function checkZone(mouseX) {
    // if mouseX is 321, it should be index 2 of zones array
}

paxdiablo · Accepted Answer · 2010-09-23T06:54:46.347

5

You can use the following loop to do it. I've included an entire page for testing purposes.

<html>
    <body>
        <script type="text/javascript">
            var i; var y = 0; var val = 321; var zones = [0,150,300,400,600,800];
            for (i = 0; i < zones.length; i++)
                if (val >= zones[i])
                    y = i;
            document.write("Value " + val + " is at position " + y);
        </script>
    </body>
</html>

Using various test data:

Value -99 is at position 0 
Value   0 is at position 0
Value 149 is at position 0
Value 150 is at position 1 
Value 321 is at position 2
Value 521 is at position 3
Value 799 is at position 4 
Value 800 is at position 5 
Value 999 is at position 5

edited Sep 23 '10 at 06:54

answered Sep 23 '10 at 05:27

paxdiablo

854,327
234
1,573
1,953

@John if performance matters to you then you might consider using the binary search method. – ErikE Sep 23 '10 at 05:45
2

Some JS-specific notes: `var` is not really optional in JavaScript, in this example seems to not make any difference, since all identifiers are global, but is not recommended because e.g., if you put the above code in a function, the identifiers will still made global, moreover, the new ECMAScript 5 [Strict Mode](http://j.mp/dzg47V) disallow assignments on undeclared identifiers. Also, the `for-in` statement might look similar to lets say, `foreach` in C#, PHP, Perl, etc, but isn't, the purpose of `for-in` is to *enumerate* object properties, the order of enumeration is not guaranteed ... – Christian C. Salvadó Sep 23 '10 at 06:02
2

... by the spec. so the properties may not be visited in the numeric order, also, inherited properties are enumerated by this statement, which can be problematic if someone extended the `Array.prototype` object -common thing even in some libraries like MooTools-. To *iterate* over an array, or an array-like object, a plain sequential loop is the best way to go. :) – Christian C. Salvadó Sep 23 '10 at 06:03
Well, that was actually _support_ code guys, meant to provide a complete example on how the loop worked, it's the loop itself that was the answer. But I'll change it to keep you happy. As to the loop itself, I've changed that as well in response to CMS' ordering comment. – paxdiablo Sep 23 '10 at 06:56
Yep the pseudocode was there, but the actual syntax could break, especially if the Array object had other property prototypes. – vol7ron Sep 23 '10 at 07:07
@pax, not just to keep us happy :), those little *JS-specific* things can cause a lot of problems if people is not aware of. It was just a heads-up. I knew it was support code -that's why I said JS-specific-, since your answer is completely valid ;) +1 from me. – Christian C. Salvadó Sep 23 '10 at 07:49

ErikE · Answer 2 · 2010-09-23T17:21:54.137

3

If your array is very large, checking each element will be slow. A binary search might be good in that case. Here's some example code (untested, but as well thought-out as I can do at this time of night):

function checkZone(mouseX) {
   var low = 0, high = zones.length, i;
   if (mouseX >= zones[high]) {
      low = high
   }
   while (high - low > 1) {
      i = low + Math.floor((high - low) / 2);
      if (mouseX >= zones[i]) {
         low = i;
      } else {
         high = i;
      }
   }
   return zones[low];
}

Note: I tried posting this about 15 minutes ago but SO ate my answer and I had to redo most of it.

edited Sep 23 '10 at 17:21

answered Sep 23 '10 at 05:43

ErikE

48,881
23
151
196

This is only good if the array is large, otherwise it's faster to iterate over each element until found because there are less conditions to evaluate. – vol7ron Sep 23 '10 at 06:20
1

@vol That **is** what I said, first sentence in my post. Thanks for reinforcing it, though. I guess. :) – ErikE Sep 23 '10 at 06:25
1

Yes, the first part of what I said reinforced. The second part I added with just a little more explanation. Nice algorithms combine the two. It starts off with the binary and then once it gets to a certain number left, it switches to literal enumerated comparison. – vol7ron Sep 23 '10 at 06:43
@vol I also would like to know who voted my answer down and why. My answer is carefully qualified so as not to be misleading, and possibly a good solution. What gives? – ErikE Sep 24 '10 at 00:31

score 0 · Answer 3 · answered Sep 23 '10 at 05:22

0

Is the array of numbers sorted in ascending order? If it is, then you have two options. If the size of array is relatively small, just iterate through it with a cycle, and find the appropriate zone. Otherwise implement a binary search (much faster).

answered Sep 23 '10 at 05:22

SPIRiT_1984

2,717
3
29
46

Yes, it is in ascending order. The size of array is small, but can be large in the future. Thanks, I'll give it a try. – John Sep 23 '10 at 05:27

vol7ron · Answer 4 · 2010-09-23T06:30:48.353

-1

This should be better and faster:

   console.clear();

   var zones = [800, 400, 150, 0, 300, 600];               // unsorted array
   zones.sort();                                           // sort for function comparison
   console.log(zones);

   function checkZone(mouseX) {
      for( var i = (zones.length-1); mouseX < zones[i--];){ }
      return ++i;
   }


   // perform 25 tests with random mouseX values 0-1000
   for (var rnd=1,runs=25; runs-- && (rnd=Math.floor( Math.random()*1000 ))>=0; ){
      console.log( (25-runs)    + ".  "
                  + "mouseX:"   + rnd  + " , "
                  + "index:"    + checkZone(rnd)           // checkZone(number) is all that's really needed
                 ); 
   }

The for-loop in the function searches the array from the last array value to the beginning. Once the param is no longer less than the array value, the loop quits and the function returns that element. We have to add one to the return variable because the loop doesn't add 1 back when the loop condition fails.

If you don't feel comfortable with console.log, you can replace it with document.write or alert. When finished testing, all that's needed is the sorted array, the function, and the function call. You can scrap the testing loop and all the random number jibber-jabber.

Example output:

   [0, 150, 300, 400, 600, 800]
   1. mouseX:458 , index:3
   2. mouseX:17 , index:0
   3. mouseX:377 , index:2
   4. mouseX:253 , index:1
   5. mouseX:446 , index:3
   6. mouseX:764 , index:4
   7. mouseX:619 , index:4
   8. mouseX:653 , index:4
   9. mouseX:337 , index:2
   10. mouseX:396 , index:2
   11. mouseX:107 , index:0
   12. mouseX:820 , index:5
   13. mouseX:850 , index:5
   14. mouseX:117 , index:0
   15. mouseX:659 , index:4
   16. mouseX:393 , index:2
   17. mouseX:906 , index:5
   18. mouseX:128 , index:0
   19. mouseX:435 , index:3
   20. mouseX:712 , index:4
   21. mouseX:841 , index:5
   22. mouseX:259 , index:1
   23. mouseX:447 , index:3
   24. mouseX:809 , index:5
   25. mouseX:892 , index:5

edited Sep 23 '10 at 06:30

answered Sep 23 '10 at 05:48

vol7ron

40,809
21
119
172

1

If you're going to step backwards through the array, the fastest javascript way to do that is `while (i--) { }`, not a `for` loop. – ErikE Sep 23 '10 at 06:28
1

That is wrong; not exactly wrong, but not always right. `for(i; i--;){}` is faster/equal. It's more on the "equal" side since it varies. See my [JSFiddle](http://jsfiddle.net/FZqZN/3409/) as part of my response to [the fastest summation question](http://stackoverflow.com/questions/3762589/fastest-javascript-summation/3762735#3762735). This reverse-for-loop is essentially the same thing as a reverse-while-loop, but there are benefits to the for-loop's caching, which gives it a minor edge. – vol7ron Sep 23 '10 at 06:46
It seems I'm being stalked by someone who doesn't like to hear their answer was bad. Aside from Emtucifor's binary algorithm addition, which doesn't apply to the small array size given in the question, my solution is the best. – vol7ron Sep 23 '10 at 07:00
Ha ha, I assume that was a jibe at me, vol7ron. Rest assured I'll leave a reason if I vote you down. However, you may want to think about learning a little modesty and/or humility. In the end, it's the community and OP that decide the best answers, not the answerers themselves. – paxdiablo Sep 23 '10 at 07:17
@paxdiablo: no, this comes from another question. Someone is following my questions/answers and downvoting all of them - a reason why SO's anonymity is shotty; I like your answer and I like Emtucifor's answer; they both are a possible solution, thus are valid answers - I still prefer mine, though. – vol7ron Sep 23 '10 at 16:02
1

Hmmm that's interesting @vol, I guess I was believing what I'd read once about `while (i--) {};`. – ErikE Sep 23 '10 at 16:12
[@Emtucifor:](http://stackoverflow.com/users/57611/emtucifor) I think what you read is still right, but no one really tested a reverse-for the same way. Internally, I think the interpreter is doing the same thing, which is why the ranking b/t the two are inconsistent - the differences are caused by the problems with the benchmark test itself (cpu/ram). I only prefer the `for` method because I can control the variable and loop condition in one place. – vol7ron Sep 23 '10 at 16:42

Logic for checking in-between two numbers

4 Answers4