在排序列表中查找最近/最近的值
我想知道是否有可能在List找到不存在的元素中最接近的元素。
例如，如果我们有值[1,3,6,7]并且我们正在寻找最接近4的元素，它应该返回3，因为3是数组中的最大数字，小于4。
我希望这是有道理的，因为英语不是我的母语。
如果数组已排序，您可以在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]; }
你需要Array.binarySearch ， docs 。
返回：搜索键的索引（如果它包含在数组中）; 否则，（ – （插入点） – 1）。 插入点定义为键将插入到数组中的点：第一个元素的索引大于键，或者如果数组中的所有元素都小于指定键，则为a.length。
考虑使用NavigableSet ，特别是higher和lower 。
似乎最简单的方法就是迭代排序列表，检查每个项目。
List 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);
这将输出列表中小于或等于target的最大项目。
另一个使用二进制搜索的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+(hl)/2; if(Math.abs(target-arr[mid])
安德烈的回答是正确的。 只是扩展一下。
当您可以使用内置二进制搜索时，无需重新发明轮子。
你可以找到索引：
int leftIndex = (-Collections.binarySearch(allItems, key) - 2); int rightIndex = (-Collections.binarySearch(allItems, key) - 1);
列表中的项目需要实现Comparable 。 像String和Integer这样的简单类型已经实现了这一点。 这是一个示例https://www.javatpoint.com/Comparable-interface-in-collection-framework 。
根据您的使用情况，您可能希望在二进制搜索之后执行index = Math.max(0, index)以确保安全。
想一想我的头脑，如果你需要在排序列表中找到所有最接近的值，你可以找到一个最接近的值，然后找到距离目标相同距离的所有值。 在这里，我使用二次搜索3次：
- 首先要找到最接近的值
- 第二，找到最左边的最近值
- 第三，找到最接近的最接近的值
在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)