Java 在排序列表中查找最近/最近的值

Find the nearest/closest value in a sorted List

提问by drBet

I was wondering if it is possible to find the closest element in a Listfor a element that is notthere.

我想知道是否有可能找到一个最接近的元素List的元素，是不是在那里。

For example if we had the values [1,3,6,7] and we are looking for the element closest to 4, it should return 3, because 3 is the biggest number in the array, that is smaller than 4.

例如，如果我们有值 [1,3,6,7] 并且我们正在寻找最接近 4 的元素，它应该返回 3，因为 3 是数组中最大的数字，它小于 4。

I hope it makes sense, because English is not my native language.

我希望这是有道理的，因为英语不是我的母语。

采纳答案by David Soroko

If the array is sorted you can do a modified binary search in O( log n ):

如果数组已排序，您可以在以下位置进行修改的二进制搜索O( log n )：

    public static int search(int value, int[] a) {

        if(value < a[0]) {
            return a[0];
        }
        if(value > a[a.length-1]) {
            return a[a.length-1];
        }

        int lo = 0;
        int hi = a.length - 1;

        while (lo <= hi) {
            int mid = (hi + lo) / 2;

            if (value < a[mid]) {
                hi = mid - 1;
            } else if (value > a[mid]) {
                lo = mid + 1;
            } else {
                return a[mid];
            }
        }
        // lo == hi + 1
        return (a[lo] - value) < (value - a[hi]) ? a[lo] : a[hi];
    }

回答by Andrey

You need Array.binarySearch, docs.

你需要Array.binarySearch，文档。

Returns: index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key.

返回： 搜索关键字的索引，如果它包含在数组中；否则，(-(插入点) - 1)。插入点定义为将键插入数组的点：大于键的第一个元素的索引，如果数组中的所有元素都小于指定的键，则为 a.length。

回答by starf

It seems like the easiest way is simply to iterate over the sorted list, checking each item.

似乎最简单的方法是简单地遍历排序列表，检查每个项目。

List<Integer> ints = new ArrayList<>();
ints.add(1);
ints.add(3);
ints.add(6);
ints.add(7);

Collections.sort(ints);

int target = 4;
int nearest = 0;

for (int i : ints)
{
    if (i <= target) {
        nearest = i;
    }
}

System.out.println(nearest);

This outputs the largest item in the list which is less than or equal to the target.

这将输出列表中小于或等于 的最大项target。

回答by Steve Kuo

Considering using NavigableSet, in particular higherand lower.

考虑使用NavigableSet，特别是higher和lower。

回答by richizy

Just thinking off the top of my head, if you need to find all closest values in a sorted list, you can find aclosest value, then find all values with the same distance away from the target. Here, I use binary search 3 times:

只是想一想，如果您需要在排序列表中找到所有最接近的值，您可以找到一个最接近的值，然后找到与目标距离相同的所有值。在这里，我使用了 3 次二分搜索：

• First to find aclosest value
• Second to find the left-most closest value
• Third to find the right-most closest value

• 首先找一个最接近的值
• 第二个找到最左边的最接近值
• 第三个找到最右边的最接近的值

In Python:

在 Python 中：

def closest_value(arr, target):
  def helper(arr, target, lo, hi, closest_so_far):
    # Edge case
    if lo == hi:
      mid = lo
      if abs(arr[mid] - target) < abs(arr[closest_so_far] - target):
        closest_so_far = mid
      return closest_so_far

    # General case
    mid = ((hi - lo) >> 1) + lo

    if arr[mid] == target:
      return mid

    if abs(arr[mid] - target) < abs(arr[closest_so_far] - target):
      closest_so_far = mid

    if arr[mid] < target:
      # Search right
      return helper(arr, target, min(mid + 1, hi), hi, closest_so_far)
    else:
      # Search left
      return helper(arr, target, lo, max(mid - 1, lo), closest_so_far)


  if len(arr) == 0:
    return -1
  return helper(arr, target, 0, len(arr) - 1, arr[0])


arr = [0, 10, 14, 27, 28, 30, 47]

attempt = closest_value(arr, 26)
print(attempt, arr[attempt])
assert attempt == 3

attempt = closest_value(arr, 29)
print(attempt, arr[attempt])
assert attempt in (4, 5)


def closest_values(arr, target):
  def left_helper(arr, target, abs_diff, lo, hi):
    # Base case
    if lo == hi:
      diff = arr[lo] - target
      if abs(diff) == abs_diff:
        return lo
      else:
        return lo + 1

    # General case
    mid = ((hi - lo) >> 1) + lo
    diff = arr[mid] - target
    if diff < 0 and abs(diff) > abs_diff:
      # Search right
      return left_helper(arr, target, abs_diff, min(mid + 1, hi), hi)
    elif abs(diff) == abs_diff:
      # Search left
      return left_helper(arr, target, abs_diff, lo, max(mid - 1, lo))
    else:
      # Search left
      return left_helper(arr, target, abs_diff, lo, max(mid - 1, lo))


  def right_helper(arr, target, abs_diff, lo, hi):
    # Base case
    if lo == hi:
      diff = arr[lo] - target
      if abs(diff) == abs_diff:
        return lo
      else:
        return lo - 1

    # General case
    mid = ((hi - lo) >> 1) + lo
    diff = arr[mid] - target
    if diff < 0 and abs(diff) > abs_diff:
      # Search right
      return right_helper(arr, target, abs_diff, min(mid + 1, hi), hi)
    elif abs(diff) == abs_diff:
      # Search right
      return right_helper(arr, target, abs_diff, min(mid + 1, hi), hi)
    else:
      # Search left
      return right_helper(arr, target, abs_diff, lo, max(mid - 1, lo))


  a_closest_value = closest_value(arr, target)
  if a_closest_value == -1:
    return -1, -1

  n = len(arr)
  abs_diff = abs(arr[a_closest_value] - target)
  left = left_helper(arr, target, abs_diff, 0, a_closest_value)
  right = right_helper(arr, target, abs_diff, a_closest_value, n - 1)
  return left, right


arr = [0, 10, 14, 27, 27, 29, 30]

attempt = closest_values(arr, 28)
print(attempt, arr[attempt[0] : attempt[1] + 1])
assert attempt == (3, 5)

attempt = closest_values(arr, 27)
print(attempt, arr[attempt[0] : attempt[1] + 1])
assert attempt == (3, 4)

回答by NewUser

Another O(log n) easy to understand solution using binary search:

另一个使用二进制搜索的 O(log n) 易于理解的解决方案：

public class Solution {
    static int findClosest(int arr[], int n, int target)
    {
        int l=0, h=n-1, diff=Integer.MAX_VALUE, val=arr[0];
        while(l<=h)
        {
            int mid=l+(h-l)/2;
            if(Math.abs(target-arr[mid])<diff)
            {
                diff= Math.abs(target-arr[mid]);
                val=arr[mid];
            }
            if(arr[mid]<target)
                l=mid+1;
            else
                h=mid-1;
        }
        return val;

    }

    public static void main(String[] args) {
        System.out.println(findClosest(new int[]{1,3,6,7}, 4, 3));
    }
}

回答by Markymark

Andrey's answer is correct. Just expanding on it a bit.
No need to reinvent the wheel when you can use the built in binary search.

安德烈的回答是正确的。只是稍微扩展一下。
当您可以使用内置的二分搜索时，无需重新发明轮子。

You can find the indices with:

您可以通过以下方式找到索引：

int leftIndex = (-Collections.binarySearch(allItems, key) - 2);
int rightIndex = (-Collections.binarySearch(allItems, key) - 1);

The item in the list will need to implement Comparable. Simple types like Stringand Integeralready implement this. Here's an example https://www.javatpoint.com/Comparable-interface-in-collection-framework.

列表中的项目需要实现Comparable。简单的类型，如String与Integer已经实现了这一点。这是一个示例https://www.javatpoint.com/Comparable-interface-in-collection-framework。

Depending on your use case you may want to do index = Math.max(0, index)after the binary search just to be safe.

根据您的用例，index = Math.max(0, index)为了安全起见，您可能希望在二进制搜索之后进行。