10 Replies Latest reply on Feb 14, 2010 7:43 PM by 843789

    How to get numbers within a range without looping?

    843789
      I've been on this problem for days now and I could really use some help.

      Let's say I have all the numbers from 1 through 10.

      How could I get all the numbers that are >3 and <7 without looping?

      Is this even possible? What strategy could I use to achieve this?

      Thanks
        • 1. Re: How to get numbers within a range without looping?
          699554
          Darkalfx wrote:
          Let's say I have all the numbers from 1 through 10.
          Are they sorted?

          Are they in an array? Is the solution limited to arrays? Are other data structures allowed?

          Is using a method that uses a underlying loop mechanism considered cheating?

          Possibly easier if you just link the question directly from where it came from.

          Mel
          • 2. Re: How to get numbers within a range without looping?
            843789
            This question came to me, because I'm trying to find a way to increase performance.
            Example: I have a sorted array with all the numbers from 1 through 10.
            I'm trying to understand how I could find all the numbers within a specific range without looping.

            But so far, this has me stumped :/
            • 3. Re: How to get numbers within a range without looping?
              843789
              The smallest number >3 is 4 and it is at index 3 of your array. The greatest number <7 is 6 and it is at position 5 in the array. Since the array is sorted you can get the ones satisfying both conditions with:
              Arrays.copyOfRange(arr, 3, 6);
              • 4. Re: How to get numbers within a range without looping?
                699554
                Darkalfx wrote:
                This question came to me, because I'm trying to find a way to increase performance.
                What sort of performance hit are you taking? I ask this because I highly doubt there is an issue present. If I am wrong then post your current implementation so that others can critique it.
                Example: I have a sorted array with all the numbers from 1 through 10.
                I'm trying to understand how I could find all the numbers within a specific range without looping.
                I don't quite understand the problem. To find the numbers in a sorted array consisting of values 1-10 is elementary. They are indexes (n-1) to (m-1) inclusive where n is the lower bound number and m is the upper bound number.

                And if you need to extract the elements into a new array simply use Arrays.copyOfRange(). But at the end of the day, I would be very surprised if no form of implicit looping occurs in Arrays.copy() in favor of magic!

                Mel
                • 5. Re: How to get numbers within a range without looping?
                  843789
                  I think part of the problem is that haven't really heard what the problem is.

                  Here's a guess: suppose I have a truck load of integers in an array and some expensive to compute condition. All I know is that the array elements that satisfy the condition lie in a contiguous section of the array. I don't really want "to get the integers" - in fact I already have them in the array! - what I really want to do is calculate the sub array bounds. And for that I might use a binary search. (or some other search algorithm). And I may also be able to contrive things so I can start with a reasonable guess.
                  • 6. Re: How to get numbers within a range without looping?
                    843789
                    pbrockway2 wrote:
                    I think part of the problem is that haven't really heard what the problem is.

                    Here's a guess: suppose I have a truck load of integers in an array and some expensive to compute condition. All I know is that the array elements that satisfy the condition lie in a contiguous section of the array. I don't really want "to get the integers" - in fact I already have them in the array! - what I really want to do is calculate the sub array bounds. And for that I might use a binary search. (or some other search algorithm). And I may also be able to contrive things so I can start with a reasonable guess.
                    That's pretty much my problem, except you explained it way better than I did.
                    • 7. Re: How to get numbers within a range without looping?
                      699554
                      pbrockway, please tell me the source of your crystal ball.
                      • 8. Re: How to get numbers within a range without looping?
                        699554
                        Darkalfx wrote:
                        pbrockway2 wrote:
                        I think part of the problem is that haven't really heard what the problem is.

                        Here's a guess: suppose I have a truck load of integers in an array and some expensive to compute condition. All I know is that the array elements that satisfy the condition lie in a contiguous section of the array. I don't really want "to get the integers" - in fact I already have them in the array! - what I really want to do is calculate the sub array bounds. And for that I might use a binary search. (or some other search algorithm). And I may also be able to contrive things so I can start with a reasonable guess.
                        That's pretty much my problem, except you explained it way better than I did.
                        Just to state how now that the actual problem has been established:

                        Refer to the Java API for Arrays. Specifically binarySearch() which takes as parameters a sorted array to be searched and a key to be searched for. If the array is not sorted then refer to the Java API for sort() contained in the same Class (Arrays).

                        Mel
                        • 9. Re: How to get numbers within a range without looping?
                          darrylburke
                          Melanie_Green wrote:
                          pbrockway, please tell me the source of your crystal ball.
                          Believe me, you really don't want to know the details of his wartime injuries...
                          • 10. Re: How to get numbers within a range without looping?
                            843789
                            That's pretty much my problem
                            Great. Post back if you have problems searching for the subarray endpoints.

                            Sometimes I wonder if the ability to divine the problems posted here isn't, in fact, a bad sign... (OP: this shouldn't be taken as a slight on you. If we could explain a problem clearly the chances are it would't be a problem any more.)