How can you find the nearest value in a list in the following case?-CodePudding

Let's assume that I have a list of the following objects:

class Row{
   int a;
   int b;
}

Data is set up in a way in which if sorted by a, the data automatically gets sorted by b. I need to write a function that takes in the parameters (int x, List<Row> rows) which finds the row whose b comes right after x. The number of records is 1000 so the basic and easy way to do it is to sort by a and then find the nearest element by using iteration. Is there another way to structure data in way in which I don't have to iterate through the entire list?

CodePudding user response：

The simplest way to do this is by starting from a sorted list. Once the list is sorted, you can use a binary search to reduce the possible value down to 2, instead of finding an exact match like you would normally do when searching.

Another thing you will need to do is establish two base cases which will help you avoid index out of bound issues: The two cases are,

If the value is less than or equal to than the smallest number in the list, return list(0).
If the value is greater than or equal to the largest number in the list, return list(size - 1).

Once the bases cases are tried, then simply use binary search to reduce your choices to two values. Then all you need to do is compare the absolute values of the difference between the actual value and the number stored in the indices of the two choices in the list.

public class ClosestInteger {
    public static void main(String[] args) {

        List<Integer> values = List.of(-23, -21, -3, 0, 1, 2, 3, 5, 8, 13, 44);
        
        for (int i = 0; i < 10; i  ) {
            Random rand = new Random();
            int value = rand.nextInt(-50, 50);
            System.out.println("Closest value to "   value   ": "   closestValue(values, value));
        }
    }

    private static int closestValue(List<Integer> list, int value) {
        if (list== null || list.isEmpty()) {
            throw new IllegalArgumentException("List cannot be null or empty");
        }
        
        if (value <= list.get(0)) {
            return list.get(0);
        }
        
        if (value >= list.get(list.size() - 1)) {
            return list.get(list.size() - 1);
        }
        
        int left = 0, right = list.size() - 1, mid = 0;
        
        while (left <= right) {
            mid = left   (right - left) / 2;

            if (list.get(mid) == value)
                return value;

            if (list.get(mid) < value) {
                left = mid   1;
            }

            else {
                right = mid - 1;
            }
        }
        
        return  Math.abs(value - list.get(left)) <= Math.abs(value - list.get(right)) ? list.get(left) : list.get(right);
    }
}

I came up with the following lambda function to find the closest integer (albeit, it might be slower than the one above - O(n)?)

private static int closestValue(List<Integer> list, int value) {
    return list.stream()
        .sorted(Comparator.comparingInt(i -> Math.abs(i - value)))
        .limit(1).findFirst().get();
}

Sample runs:

Closest value to 17: 13
Closest value to 28: 13
Closest value to -26: -23
Closest value to 22: 13
Closest value to 0: 0
Closest value to -10: -3
Closest value to -11: -3
Closest value to -24: -23
Closest value to -33: -23
Closest value to -40: -23

Closest value to 15: 13
Closest value to 3: 3
Closest value to -26: -23
Closest value to -13: -21
Closest value to -6: -3
Closest value to 12: 13
Closest value to 43: 44
Closest value to -37: -23
Closest value to 1: 1
Closest value to 4: 5

Closest value to 10: 8
Closest value to 22: 13
Closest value to 7: 8
Closest value to -50: -23
Closest value to -20: -21
Closest value to -50: -23
Closest value to 25: 13
Closest value to 20: 13
Closest value to -31: -23
Closest value to -41: -23

CodePudding user response：

You can use Collections.binarySearch() like this.

static class Row {
    int a, b; 
    public int getA() { return a; } 
    public int getB() { return b; } 
    Row(int a, int b) { this.a = a; this.b = b; } 
    @Override public String toString() { return "Row("   a   ", "   b   ")"; }
}

static final Comparator<Row> ORDER_BY_B = Comparator.comparing(Row::getB);

static Row find(int x, List<Row> rows) {
    int size = rows.size();
    int i = Collections.binarySearch(rows, new Row(0, x), ORDER_BY_B);
    int index = i >= 0 ? i : i <= -size - 1 ? size - 1 : -i - 1;
    return rows.get(index);
}

public static void main(String[] args) {
    List<Row> rows = Arrays.asList(
        new Row(20, 2),
        new Row(40, 4),
        new Row(50, 5),
        new Row(70, 7));
    List<Row> orderByB = rows.stream().sorted(ORDER_BY_B).collect(Collectors.toList());
    for (int i = 0; i < 9;   i)
        System.out.println("find "   i   " : "   find(i, orderByB));
}

output:

find 0 : Row(20, 2)
find 1 : Row(20, 2)
find 2 : Row(20, 2)
find 3 : Row(40, 4)
find 4 : Row(40, 4)
find 5 : Row(50, 5)
find 6 : Row(70, 7)
find 7 : Row(70, 7)
find 8 : Row(70, 7)