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

Question

我有一个二进制向量的排序列表，我们称之为 L，我有一个二进制向量 q，如何使用二进制搜索找到 L 中最接近 q 的向量？

Answer 1

如果您将最近的定义为两个向量之间的距离。这是查找最接近向量的伪代码。

Vector closestVector = null;
Vector findClosestVector(L,q)
{

     int i= L.lenght/2;
     if(i ==1 ) 
     {
           Vector v = L.get(0);
           int distance = distance(v,q);
           if(closestVector == null)
           {
                   closestVector = v;
           }
           else {
               int d1 = distance(closestVector,q);
               if(d1 > distance) {
                     closestVector = v;
                     return v;
                 }
           }

     }
     else
     {
           Vector left = findClosestVector(L(0,L/2),q);
           Vector right = findClosestVector(L(L/2,L),q);
           if(distance(left,q) > distance(right,q))
           {
                return right;
           }
           else
           {
               return left;
           }
     }

 }

}

Answer 2

既然你说你有一个排序的向量列表，我假设“最接近”是指就该排序而言最接近另一个向量。你可以使用java.util.Arrays.binarySearch它。它返回：

搜索键的索引，如果它包含在数组中；否则，（-插入点- 1）。插入点定义为将键插入数组的点。

所以如果向量q在数组中，你会发现它的索引和它的邻居最接近它。如果不是，您将找到一个索引j = -i - 1（i是 的结果） ，binarySearch其中q将被插入，然后是最接近它的位置。ii-1