维基百科中使用 ceil 实现二分查找

Question

上面的实现是维基百科版本的二分搜索，

我的简单疑问是，用于计算 mid 的 ceil 函数与将 L 移动到 M 而不是 M + 1 的语句之间是否有任何关系{这是二分搜索的标准实现}

Answer 1

用于计算mid的ceil函数和将L移动到M而不是M + 1的语句之间有什么关系吗

是的，有关系。更常见的是使用

floor

函数，或者类似地，使用整数除法运算符。在这种情况下，L 或 M 的更新方式会有所不同。如果我们重写您引用的代码以使用

floor

，那么它可能看起来像这样

使用

floor

的版本：

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else:
            R := m
    if A[L] = T then
        return L
    return unsuccessful

循环的主体与您引用的代码不同，我在这里再次提供：

使用

ceil

的版本：

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m − 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

至少有两点需要注意：

当
```
T
```
等于
```
A[m]
```
时执行的块应该将
```
m
```
分配给窗口的边界之一，而不是
```
m+1
```
或
```
m-1
```
，因为这会排除潜在的匹配来自窗口的值。在您引用的代码中，当存在相等时会执行
```
else
```
块，因此存在
```
L := m + 1
```
是错误的。
我们不能在
m和
```
if
```
块中分配
```
else
```
，因为这可能会导致无限循环。这是因为您必须确保窗口在每次迭代时变得更小：必须保证这一点。需要注意的一个很好的测试是当
```
L
```
和
```
R
```
相差一个单位时。

在这种情况下，
```
ceil
```
函数将返回
```
R
```
的值，而
```
floor
```
函数将返回
```
L
```
的值。如果我们有
```
m == R
```
（
```
ceil
```
版本），那么当您对
```
R
```
进行分配时，您必须确保它小于 R
```
，即它应该获得值 
```
m - 1
```
 而不是 
```
m
```
。如果我们有 
```
m == L
```
（
```
floor
```
 版本），那么我们应该分配 
```
L := m + 1
```
 而不是 
```
L := m
```
。
```

注意这两个版本如何真正相互

镜像：R

和

L

交换，比较运算符切换（

<

与

>

）以及

- 1

和

+ 1

彼此镜像。这对应于

floor

和

ceil

 彼此镜像的方式。

我们也可以修改循环后的语句来完美完成镜像，并将这部分代码中的

L

替换为

R

，但是由于当

A

不为空时这两个变量相等，因此不会其实并不重要。

该函数实际上应该包括检查

A

 是否为空，因为我们不想在这种情况下评估

A[L]

 ，甚至不想最终进入循环。因此，在这两种情况下，函数最好将其放在顶部：

    if n = 0 then
        return unsuccessful

维基百科中使用 ceil 实现二分查找

问题描述投票：0回答：1

1个回答

最新问题

维基百科中使用 ceil 实现二分查找

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1