0

据我所见，while循环指定的二进制搜索应该始终继续搜索，直到搜索空间的最小值和最大值相等。但是在测试它时，并且总是在已经对大部分项目进行排序之后，它会陷入无限循环，因为mx以某种方式获得了价值-2。

我想我可以改变 while 循环的条件来修补它，但我试图理解它为什么会这样，并尝试用我的眼睛和纸上的方式检查它，但无法重现 where 的事件mx = -2。

def insort(seq):
    for a in xrange(1, len(seq)):
        if seq[a] > seq[a - 1]:
            continue
        else:
            mn, mx = 0, a - 1
            while mn != mx:
                pivot = mn + ((mx - mn) / 2)
                if seq[a] > seq[pivot]:
                    mn = pivot + 1
                else:
                    mx = pivot - 1
            seq.insert(mn, seq.pop(a))
4

1 回答 1

3

注意：我使用的是 python 2.7.3。我不确定其他版本的python是否会因除法而产生不同的结果，所以这里提个醒。

需要进行几处更改：

  • 更改mn != mx为mn < mx
  • 更改pivot = mn + ((mx - mn) / 2)声明以pivot = int(math.floor((mn + mx) / 2))防止pivot = mn + int(math.floor((mx - mn) / 2))在涉及分裂时出现任何意外。
  • mn由 指示的搜索间隔mx更改为由 给出的半开间隔，[mn, mx)因为这是我在手动编码二进制搜索时更熟悉的内容。somx应该设置为a最初，并且mx应该设置为pivot而不是pivot - 1在 where seq[a] <= seq[pivot](iow, if the iftest is False) 的情况下。

因此，经过编辑的代码应如下所示：

import math

def insort(seq):
    for a in xrange(1, len(seq)):
        if seq[a] > seq[a - 1]:
            continue
        else:
            mn, mx = 0, a
            while mn < mx:
                pivot = mn + int(math.floor(((mx - mn) / 2)))
                if seq[a] > seq[pivot]:
                    mn = pivot + 1
                else:
                    mx = pivot
            seq.insert(mn, seq.pop(a))

对于原始代码，我会给你一个mx卡住的例子-2。

鉴于此列表：[10, 7, 8, 5, 13, 2, 6, 1, 50]

一切正常，直到索引 5 处的元素，其值为2（通过添加一些print语句自行验证）。由于seq[a] > seq[a-1]is false （2是迄今为止最小的元素），我们进入 if 语句的 else 分支。

在此刻：

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = a - 1 = 4

从mn != mx( 0 != 4) 开始，我们进入 while 循环。pivot设置为0 + ((4 - 0) / 2)= 2。接下来我们执行if seq[a] > seq[pivot]。seq[a] = 2, while seq[pivot]= 8and 2 > 8is False, 所以我们去 else 分支并执行mx = pivot - 1 = 2 - 1 = 1

在此刻：

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = 1

我们再次在 while 循环中执行检查。mn != mx( 0 != 1)，所以我们进入 while 循环的主体。我们设置pivot = 0 + ((1 - 0) / 2) = 0（我使用python 2.7来执行这个除法，所以在repl处进行验证），然后执行检查seq[a] > seq[pivot]（2 > 5），即False. 因此，我们设置mx = pivot - 1 = 0 - 1 = -1。

在此刻：

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = -1

mn != mx现在，我们在 while 循环( )处执行检查0 != -1，因此我们进入 while 循环的主体。pivot = 0 + ((-1 - 0) / 2) = -1. 然后我们执行检查seq[a] > seq[pivot]( seq[5] > seq[-1]，将第 5 个元素与 的最后一个元素进行比较seq，换句话说2 > 50)，即False。所以mx = pivot - 1 = -1 - 1 = -2。

现在我们已经到了最后一步：

seq = [5, 7, 8, 10, 13, 2, 6, 1, 50]
a = 5
mn = 0
mx = -2

在 while 循环检查，mn != mx，所以我们继续pivot = 0 + ((-2 - 0) / 2) = -1。请注意，这与上述步骤相同。然后seq[5] > seq[-1]执行 ( 2 > 50)，即False。所以mx = pivot - 1 = -1 - 1 = -2。我们最终处于与上述相同的状态。这就是为什么你会看到一个无限循环。

最后，我只想说，二分搜索是一个非常棘手的算法，因为它很容易在边界索引上出错。我已经手动编写了很多次代码，但我仍然觉得它很棘手。您可能还想阅读此内容：http ://en.wikipedia.org/wiki/Binary_search_algorithm

希望有帮助！

于 2013-08-05T03:26:20.487 回答