Finding the Closest Number to a Given Value From a List of Integers in Java | Baeldung

1. Overview

When we work with integer Lists in Java, one common problem we may encounter is finding the number in a List that is closest to a given value.

In this tutorial, we’ll explore different ways to solve this problem using Java.

2. Introduction to the Problem

Let’s first look at the definition of the problem:

Given a List of integers and a target value, we need to find the number from the List that is closest to the target. We pick the one with the lowest index if multiple numbers are equally close.

Next, let’s quickly understand the “distance” between a number and a given target.

2.1. The Distance Between Two Numbers

In this context, the distance between numbers a and b is the absolute value of a – b: Distance = abs(a – b)

For instance, given target = 42, the following are the distances (D) between target and different numbers (n):

n = 42 → D = abs(42 – 42) = 0
n = 100 → D = abs(42 – 100) = 58
n = 44 → D = abs(42 – 44) = 2
n = 40 → D = abs(42 – 40) = 2

As we can see, given target = 42, numbers 44 and 40 are the same distance from the target.

2.2. Understanding the Problem

So, the closest number to the target in a List has the smallest distance to the target among all elements. For example, in the List:

[ 8, 100, 6, 89, -23, 77 ]

Given target = 70, the closest integer in the List to it is 77. But if target = 7, then both 8 (index: 0) and 6 (index: 2) have an equal distance (1) to it. In this case, we choose the number with the lowest index. Thus, 8 is the expected result.

For simplicity, we assume the given List isn’t null or empty. We’ll explore various approaches to solving this problem. We’ll also take this integer List as an example and leverage unit test assertions to verify each solution’s result.

Additionally, to solve the problem efficiently, we’ll choose different algorithms to solve the problem depending on whether the input List is sorted.

Next, let’s design some test cases to cover all scenarios:

When target (-100) is less than the Min. integer (-23) in the List: result = -23
When target (500) is greater than the Max. integer (100) in the List: result = 100
When target (89) exists in the List: result = 89
When target (70) doesn’t exist in the List: result = 77
If multiple integers (8 and 6) in the List have the same distance (1) to target (7): result = 8

Now, let’s dive into the code.

3. When We Don’t Know if the List Is Sorted

Commonly, we don’t know if the given List is sorted. So, let’s create a List variable to hold our numbers:

static final List<Integer> UNSORTED_LIST = List.of(8, 100, 6, 89, -23, 77);

Clearly, this isn’t a sorted List.

Next, we’ll solve the problem using two different approaches.

3.1. Using a Loop

The first idea to solve the problem is walking through the List and checking the distance between each number and target:

static int findClosestByLoop(List<Integer> numbers, int target) {
    int closest = numbers.get(0);
    int minDistance = Math.abs(target - closest);
    for (int num : numbers) {
        int distance = Math.abs(target - num);
        if (distance < minDistance) {
            closest = num;
            minDistance = distance;
        }
    }
    return closest;
}

As the code shows, we start with the first number in the List as closest, and save the distance between target and it in another variable minDistance, which keeps track of the smallest distance.

Then, we loop through the List. For each number in the List, we calculate its distance to target and compare it to minDistance. If it’s smaller than minDistance, we update closest and minDistance.

After iterating through the entire List, closest holds the final result.

Next, let’s create a test to check if this approach works as expected:

assertEquals(-23, findClosestByLoop(UNSORTED_LIST, -100));
assertEquals(100, findClosestByLoop(UNSORTED_LIST, 500));
assertEquals(89, findClosestByLoop(UNSORTED_LIST, 89));
assertEquals(77, findClosestByLoop(UNSORTED_LIST, 70));
assertEquals(8, findClosestByLoop(UNSORTED_LIST, 7));

As we can see, this loop-based solution passes all our test cases.

3.2. Using the Stream API

Java Stream API allows us to handle collections conveniently and concisely. Next, let’s solve this problem using the Stream API:

static int findClosestByStream(List<Integer> numbers, int target) {
    return numbers.stream()
      .min(Comparator.comparingInt(o -> Math.abs(o - target)))
      .get();
}

This code looks more compact than the loop-based solution. Let’s walk through it quickly to understand how it works.

First, numbers.stream() converts List to a Stream.

Then, min() finds the minimum element in the Stream based on a custom Comparator. Here, we use Comparator.comparingInt() and a lambda expression to create the custom Comparator that compares integers based on the value produced by the lambda. The lambda o -> Math.abs(o – target) effectively measures the distance between target and each number in the List.

The min() operation returns an Optional. The Optional is always present since we assume the List is not empty. Therefore, we call get() directly to extract the closest number from the Optional object.

Next, let’s check if the stream-based approach works correctly:

assertEquals(-23, findClosestByStream(UNSORTED_LIST, -100));
assertEquals(100, findClosestByStream(UNSORTED_LIST, 500));
assertEquals(89, findClosestByStream(UNSORTED_LIST, 89));
assertEquals(77, findClosestByStream(UNSORTED_LIST, 70));
assertEquals(8, findClosestByStream(UNSORTED_LIST, 7));

If we run the test, it passes. So, this solution does the job concisely and effectively.

3.3. Performance

Whether applying the straightforward loop-based or the compact stream-based approach, we must iterate through the entire List once to get the result. Therefore, both solutions have the same time complexity: O(n).

Since neither solution considers the List order*,* they work regardless of whether the given List is sorted.

However, if we know the input List is sorted, we can apply a different algorithm for better performance. Next, let’s figure out how to do it.

4. When the List Is Sorted

If the List is sorted, we can use binary search with O(log n) complexity to improve performance.

First, let’s create a sorted List containing the same numbers in previous examples:

static final List<Integer> SORTED_LIST = List.of(-23, 6, 8, 77, 89, 100);

Then, we can implement a binary-search-based method to solve the problem:

public static int findClosestByBiSearch(List<Integer> sortedNumbers, int target) {
    int first = sortedNumbers.get(0);
    if (target <= first) {
        return first;
    }
 
    int last = sortedNumbers.get(sortedNumbers.size() - 1);
    if (target >= last) {
        return last;
    }
 
    int pos = Collections.binarySearch(sortedNumbers, target);
    if (pos > 0) {
        return sortedNumbers.get(pos);
    }
    int insertPos = -(pos + 1);
    int pre = sortedNumbers.get(insertPos - 1);
    int after = sortedNumbers.get(insertPos);
 
    return Math.abs(pre - target) <= Math.abs(after - target) ? pre : after;
}

Now, let’s understand how the code works.

First, we handle two special cases:

target <= the smallest number in the List, which is the first element – Return the first element
target >= the largest number in the List, which is the last element – Return the last element

Then, we call Collections.binarySearch() to find the position (pos) of target in the sorted List. binarySearch() returns:

pos > 0 – Exact match, which means target is found in the List
pos < 0 – target is not found. The negative pos is the negated insertion point (where target would be inserted to maintain the sorted order) minus 1: pos = (- insertPos – 1)

If an exact match is found, we take the match directly, as it’s the closest number (distance = 0) to target.

Otherwise, we need to determine the closest number from two numbers before and after the insertion point (insertionPos = – (pos – 1)). Of course, the number with smaller distance wins.

This method passes the same test cases:

assertEquals(-23, findClosestByBiSearch(SORTED_LIST, -100));
assertEquals(100, findClosestByBiSearch(SORTED_LIST, 500));
assertEquals(89, findClosestByBiSearch(SORTED_LIST, 89));
assertEquals(77, findClosestByBiSearch(SORTED_LIST, 70));
assertEquals(6, findClosestByBiSearch(SORTED_LIST, 7));

It’s worth noting that given target = 7, the expected number in the last assertion is 6 instead of 8. This is because 6’s index (1) is smaller than 8’s index (2) in the sorted List.

5. Conclusion

In this article, we’ve explored two approaches to finding the number closest to a given value from a List of integers. Also, if the List is sorted, we can use binary search to find the closest number efficiently with a time complexity of O(log n).

As always, the complete source code for the examples is available over on GitHub.

Persistence

REST

Security