CODEWITHSUNDEEP
java
Manuel Selva
Manuel Selva

Reputation: 19050

Find closest value in an ordered list

I am wondering how you would write a simple java method finding the closest Integer to a given value in a sorted Integer list.

Here is my first attempt:

public class Closest {

    private static List<Integer> integers = new ArrayList<Integer>();

    static {
        for (int i = 0; i <= 10; i++) {
            integers.add(Integer.valueOf(i * 10));
        }
    }

    public static void main(String[] args) {

        Integer closest = null;
        Integer arg = Integer.valueOf(args[0]);

        int index = Collections.binarySearch(
                integers, arg);

        if (index < 0) /*arg doesn't exist in integers*/ {
            index = -index - 1;
            if (index == integers.size()) {
                closest = integers.get(index - 1);
            } else if (index == 0) {
                closest = integers.get(0);
            } else {
                int previousDate = integers.get(index - 1);
                int nextDate =  integers.get(index);
                if (arg - previousDate < nextDate - arg) {
                    closest = previousDate;
                } else {
                    closest = nextDate;
                }
            }
        } else /*arg exists in integers*/ {
            closest = integers.get(index);
        }
        System.out.println("The closest Integer to " + arg + " in " + integers
                + " is " + closest);
    }
}

What do you think about this solution ? I am sure there is a cleaner way to do this job.

Maybe such method exists somewhere in the Java libraries and I missed it ?

Upvotes: 32

Views: 34557

Answers (10)

RickJo
RickJo

Reputation: 86

Probably a bit late, but this WILL work, this is a data structure binary search:

Kotlin:

fun binarySearch(list: List<Int>, valueToCompare: Int): Int {
    var central: Int
    var initialPosition = 0
    var lastPosition: Int
    var centralValue: Int
    lastPosition = list.size - 1
    while (initialPosition <= lastPosition) {
        central = (initialPosition + lastPosition) / 2 //Central index
        centralValue = list[central]                   //Central index value
        when {
            valueToCompare == centralValue -> {
                return centralValue          //found; returns position
            }
            valueToCompare < centralValue -> {
                lastPosition = central - 1  //position changes to the previous index
            }
                else -> {
                initialPosition = central + 1 //position changes to next index
                }
            }
    }
    return -1 //element not found
}

Java:

public int binarySearch(int list[], int valueToCompare) {
    int central;
    int centralValue;
    int initialPosition = 0;
    int lastPosition = list . length -1;
    while (initialPosition <= lastPosition) {
        central = (initialPosition + lastPosition) / 2; //central index
        centralValue = list[central]; //central index value
        if (valueToCompare == centralValue) {
            return centralValue; //element found; returns position
        } else if (valueToCompare < centralValue) {
            lastPosition = central - 1; //Position changes to the previous index
        } else {
            initialPosition = central + 1; //Position changes to the next index
        }
        return -1; //element not found
    }
}

I hope this helps, happy coding.

Upvotes: 1

Nicolas Duponchel
Nicolas Duponchel

Reputation: 1349

Kotlin is so helpful

fun List<Int>.closestValue(value: Int) = minBy { abs(value - it) }

val values = listOf(1, 8, 4, -6)

println(values.closestValue(-7)) // -6
println(values.closestValue(2)) // 1
println(values.closestValue(7)) // 8

List doesn't need to be sorted BTW

Edit: since kotlin 1.4, minBy is deprecated. Prefer minByOrNull

@Deprecated("Use minByOrNull instead.", ReplaceWith("this.minByOrNull(selector)"))
@DeprecatedSinceKotlin(warningSince = "1.4")

Upvotes: 25

user3367701
user3367701

Reputation: 853

A solution without binary search (takes advantage of list being sorted):

public int closest(int value, int[] sorted) {
  if(value < sorted[0])
    return sorted[0];

  int i = 1;
  for( ; i < sorted.length && value > sorted[i] ; i++);

  if(i >= sorted.length)
    return sorted[sorted.length - 1];

  return Math.abs(value - sorted[i]) < Math.abs(value - sorted[i-1]) ?
         sorted[i] : sorted[i-1];
}

Upvotes: 3

Brett Kail
Brett Kail

Reputation: 33936

Your solution appears to be asymptotically optimal. It might be slightly faster (though probably less maintainable) if it used Math.min/max. A good JIT likely has intrinsics that make these fast.

int index = Collections.binarySearch(integers, arg);
if (index < 0) {
    int previousDate = integers.get(Math.max(0, -index - 2));
    int nextDate = integers.get(Math.min(integers.size() - 1, -index - 1));
    closest = arg - previousDate < nextDate - arg ? previousDate : nextDate;
} else {
    closest = integers.get(index);
}

Upvotes: 0

SimonC
SimonC

Reputation: 6718

If you're not massively concerned on performance (given that the set is searched twice), I think using a Navigable set leads to clearer code:

public class Closest
{
  private static NavigableSet<Integer> integers = new TreeSet<Integer>();

  static
  {
    for (int i = 0; i <= 10; i++)
    {
      integers.add(Integer.valueOf(i * 10));
    }
  }

  public static void main(String[] args)
  {
    final Integer arg = Integer.valueOf(args[0]);
    final Integer lower = integers.lower(arg);
    final Integer higher = integers.higher(arg);

    final Integer closest;
    if (lower != null)
    {
      if (higher != null)
        closest = (higher - arg > arg - lower) ? lower : higher;
      else
        closest = lower;
    }
    else
      closest = higher;

    System.out.println("The closest Integer to " + arg + " in " + integers + " is " + closest);
  }
}

Upvotes: 0

Andreas Dolk
Andreas Dolk

Reputation: 114767

To solve the problem, I'd extend the Comparable Interface by a distanceTo method. The implementation of distanceTo returns a double value that represents the intended distance and which is compatible with the result of the compareTo implementation.

The following example illustrates the idea with just apples. You can exchange diameter by weight, volume or sweetness. The bag will always return the 'closest' apple (most similiar in size, wight or taste)

public interface ExtComparable<T> extends Comparable<T> {
   public double distanceTo(T other);
}

public class Apple implements Comparable<Apple> {
   private Double diameter;

   public Apple(double diameter) {
      this.diameter = diameter;
   }

   public double distanceTo(Apple o) {
      return diameter - o.diameter;
   }

   public int compareTo(Apple o) {
      return (int) Math.signum(distanceTo(o));
   }
}

public class AppleBag {
   private List<Apple> bag = new ArrayList<Apple>();

   public addApples(Apple...apples){
      bag.addAll(Arrays.asList(apples));
      Collections.sort(bag);
   }

   public removeApples(Apple...apples){
      bag.removeAll(Arrays.asList(apples));
   }

   public Apple getClosest(Apple apple) {
      Apple closest = null;
      boolean appleIsInBag = bag.contains(apple);
      if (!appleIsInBag) {
         bag.addApples(apple);
      }

      int appleIndex = bag.indexOf(apple);
      if (appleIndex = 0) {
         closest = bag.get(1);
      } else if(appleIndex = bag.size()-1) {
         closest = bag.get(bag.size()-2);
      } else {
         double absDistToPrev = Math.abs(apple.distanceTo(bag.get(appleIndex-1));
         double absDistToNext = Math.abs(apple.distanceTo(bag.get(appleIndex+1));
         closest = bag.get(absDistToNext < absDistToPrev ? next : previous);
      }

      if (!appleIsInBag) {
         bag.removeApples(apple);
      }

      return closest;
   }
}

Upvotes: 1

Galghamon
Galghamon

Reputation: 2042

I think your answer is probably the most efficient way to return a single result.

However, the problem with your approach is that there are 0 (if there is no list), 1, or 2 possible solutions. It's when you have two possible solutions to a function that your problems really start: What if this is not the final answer, but only the first in a series of steps to determine an optimal course of action, and the answer that you didn't return would have provided a better solution? The only correct thing to do would be to consider both answers and compare the results of further processing only at the end.

Think of the square root function as a somewhat analogous problem to this.

Upvotes: 0

dfa
dfa

Reputation: 116314

try this little method:

public int closest(int of, List<Integer> in) {
    int min = Integer.MAX_VALUE;
    int closest = of;

    for (int v : in) {
        final int diff = Math.abs(v - of);

        if (diff < min) {
            min = diff;
            closest = v;
        }
    }

    return closest;
}

some testcases:

private final static List<Integer> list = Arrays.asList(10, 20, 30, 40, 50);

@Test
public void closestOf21() {
    assertThat(closest(21, list), is(20));
}

@Test
public void closestOf19() {
    assertThat(closest(19, list), is(20));
}

@Test
public void closestOf20() {
    assertThat(closest(20, list), is(20));
}

Upvotes: 35

newacct
newacct

Reputation: 122429

I think what you have is about the simplest and most efficient way to do it. Finding the "closest" item in a sorted list isn't something that is commonly encountered in programming (you typically look for the one that is bigger, or the one that is smaller). The problem only makes sense for numeric types, so is not very generalizable, and thus it would be unusual to have a library function for it.

Upvotes: 0

AlbertoPL
AlbertoPL

Reputation: 11509

Certainly you can simply use a for loop to go through the and keep track of the difference between the value you are on and the value. It would look cleaner, but be much slower.

See: Finding closest match in collection of numbers

Upvotes: 0

Related Questions