java - Find largest number closest to given number in an array

Question

Let's say I have an array called ArrL that consists of numbers 5, 10, 25, 33, 22, 8 and 11. My function will take a number say 21 and find the number that is "larger than 21 and closest to 21" which in this case would be 22. How would I do this?

Answer 1

Because your comparison list isn't sorted you have to check every element in it. A sorted list could be done more efficiently with a binary search but that's not the case for your list.

The idea is to keep a record of the closest-but-greater number as you go through the list and update it where you find a better one (still greater but closer than the current saved one), something like this descriptive process:

1. For every number N in the list, perform the following steps 2 through 5 inclusive. If you're out of numbers, just go to step 6.

2. If N is less than or equal to your target number, go to step 5. It's of no interest.

3. If R hasn't yet been set (this N is the first number you've found greater than your target), save N as the return value R, then go to step 5.

4. If N is less than R, replace R with N, as it's closer.

5. Go back to step 1 for the next number.

6. If you've set R to something in those steps above, that's the value you want. Otherwise there were no values higher than your target number.

The following pseudo-code is another way of looking at it:

def greaterButClosest (list, find):

  found = -1                         # Initially none.

  for idx = 0 to list.length:        # Check all indexes.

    if list[idx] > find:             # Only consider those higher.

      if found == -1:                # First one automatically closest.
        found = idx
      else:
        if list[idx] < list[found]:  # Otherwise, closer if less than current.
          found = idx

  if found == -1:                    # Some sentinel if none found.
    return -99999

  return list[found]                 # Otherwise return it.

---

And, as proof of concept, the Python code:

def greaterButClosest (list, find):
    found = -1
    for idx in range (len(list)):
        if list[idx] > find:                   # < for opposite case.
            if found == -1:
                found = idx
            else:
                if list[idx] < list[found]:    # > for opposite case.
                    found = idx

    # <- Note indent level, this is OUTSIDE the for loop.
    if found == -1:
        return -99999
    return list[found]

for tst in [7, 8, 9, 10, 11, 99]:
    print "%2d: %2d"%(tst, greaterButClosest ([5, 10, 25, 33, 22, 8, 11], tst))

which outputs:

 7:  8
 8: 10
 9: 10
10: 11
11: 22
99: -99999