java - 如何使用二进制搜索算法找到最接近给定二进制键值的元素？

Question

我有一个二元 vector 的排序列表，我们称它为 L，我有一个二元 vector q，如何使用二分搜索在 L 中找到最接近 q 的 vector ？

Answer 1

既然你说你有一个排序的 vector 列表，我假设“最接近”是指在排序方面最接近另一个的 vector 。您可以使用 java.util.Arrays.binarySearch为了那个原因。它返回:

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.

因此，如果 vector q 在数组中，您会发现它的索引和它的邻居离它最近。如果不是，您将找到一个索引 j = -i - 1(i 是 binarySearch 的结果)，其中 q 将被插入，然后 i 和 i-1 将是最接近它的。