7

在二分查找算法中，我们有两个比较：

if (key == a[mid]) then found;

else if (key < a[mid]) then binary_search(a[],left,mid-1);
      else binary_search(a[],mid+1,right);

有没有一种方法可以让我只有一个比较而不是上述两个。

--

谢谢

阿洛克.Kr.

4

7 回答 7

15

看：

http://en.wikipedia.org/wiki/Binary_search_algorithm#Single_comparison_per_iteration

取自维基：

   low = 0
   high = N
   while (low < high) {
       mid = low + ((high - low) / 2)
       if (A[mid] < value)
           low = mid + 1;
       else
            //can't be high = mid-1: here A[mid] >= value,
            //so high can't be < mid if A[mid] == value
            high = mid;
   }
   // high == low, using high or low depends on taste
   if ((low < N) && (A[low] == value))
       return low // found
   else
       return -1 // not found

来自 wiki 的优点/缺点： “这种方法放弃了在发现匹配时提前终止的可能性，因此成功的搜索具有 log2(N) 次迭代，而不是预期的 log2(N) - 1 次迭代。另一方面，这种实现使得比较少：log2(N) 小于 1·5(log2(N) − 1) 的两次测试实现的预期比较次数，因为 N 大于 8。”

于 2010-08-17T07:30:13.177 回答
4

是的。只是不要mid从递归调用中消除。

if ( left == right ) return NULL;
if ( left + 1 == right ) return key == a[left]? &a[left] : NULL;

mid = left + ( right - left / 2 );

if (key < a[mid]) return binary_search(a[],left,mid-1);
else return binary_search(a[],mid,right); // include `mid` in next round

您只需在每次递归时消除一半的集合即可实现 O(logN) 性能。通过消除 half+1，您将超越自我。

如果只<在递归期间使用，算法会找到不小于key（但可能大于key）的最小元素。通过执行单个相等性测试来完成。

于 2010-08-17T07:23:27.777 回答
2

在汇编程序中，您可以：

cmp key,a[mid]
beq found
bge else

因此，如果您的编译器非常擅长窥视孔优化，它可能已经为您完成了这项工作。

于 2010-08-17T07:24:29.900 回答
0

这是递归算法。第一个比较是停止条件，第二个是实际搜索，因此您无法删除它们。

首先，您询问何时已经找到元素，然后询问要在数组的哪个部分查找元素。因此，您不能仅根据一次比较做出这些决定。

于 2010-08-17T07:22:37.963 回答
0

首先要做的事情是：您需要优化程序吗？你有没有测量知道你需要在哪里做？是在这个函数里吗？

对于原始类型，第二个比较是尽可能快的操作。比较的较高成本是将元素加载到适当的寄存器中，这是第一次比较所需要的。一旦执行该比较，该值已经在寄存器中，并且第二个操作需要一条处理器指令加上分支预测错误的可能成本。

假设整数类型，如果编译器无法执行尾递归优化，算法的处理器时间成本很可能主要由递归调用的成本决定。如果您确实需要对此进行优化，请尝试使用所有优化标志进行编译并分析汇编程序以确定是否正在应用尾递归优化。如果不是，请手动将算法从递归转换为迭代。

这将产生两个影响：模糊代码（避免修改干净的解决方案，除非你真的需要），它避免了函数调用。

如果您说的是 C++，并且类型很复杂并且重载的比较运算符很昂贵，那么最快的性能提升是实现一种方法，该方法将在小于、等于compare时返回负数，如果大于则返回正数-比。然后在比较之前预先计算结果，然后执行仅整数检查。这将通过昂贵的比较将算法的总体成本消除到对真实对象的单一处理，并使您回到最初的假设。0

于 2010-08-17T07:53:38.260 回答
0 
for (step = 0; step < n; step <<= 1);

for (i = 0; step; step >>= 1)
    if (i + step < n && v[i + step] <= x)
        i += step;
于 2010-08-17T13:03:16.930 回答
0

好的，这是 Adob​​e 的一个面试问题，我只是想弄清楚如何做到这一点。

现在我已经找到了解决方案，所以我正在发布

void binary_search (int a[] , int low ,  int high , int key )
{
    int mid = (low+high)/2;

    if (key == a[mid]) {
        printf ("Number Found\n");
        return;
    }

    else {
        int sign = Calc_sign (key-a[mid]);
        low = low*sign + (1-sign)*mid;
        high = mid*sign + (1-sign)*right;
        binary_search (a,low,high,key);
    }
}

int Calc_sign(int a) 
{
     return ( (a & 80000000) >> 31);
}

所以在代码中只有一个比较来检查键值是否等于中间元素。

--

谢谢

阿洛克 Kr.

于 2010-08-17T14:12:56.353 回答