02python算法-二分法简介

老规矩：

什么是二分法：

　　其实是一个数学领域的词，但是在计算机领域也有广泛的使用。

为什么需要二分法？

当穷举算法性能让你崩溃时。

二分法怎么用呢？

让我们先玩一个游戏先，我心里想一个100以内的整数你来猜猜。那么你可以从1-100这么猜，当然如果我说我想的10000以内的，那么迭代次数线性上升。。。你懂的
当然你可以先设一个猜想数，我们可以采用2分之一的方法猜，首先是50 那么比50大的化就在50-100取2分之一为猜想数，继续。当然2分法不一定是2分之一，只是取决

于答案出现的区间十分有规律性，如果你知道小明老是喜欢猜比较小的数，你会不会一直都用2分之一呢？

我们可以看下用二分法排序的代码

def quick (L, low, high):

    i = low

    j = high

    if i >= j:

        return L

    key = L[i]

    while i < j:

        while i < j and L[j] >= key:

            j = j-1

        L[i] = L[j]

        while i < j and L[i] <= key:

            i = i+1

        L[j] = L[i]

    L[i] = key

    quickSort(L, low, i-1)

    quickSort(L, j+1, high)

    return L

　　很简单吧，这个是用递归实现的，核心依然是猜想数. 先设置一个猜想数，然后比猜想大的在右边，比猜想数小的在左边。然后把一个列表分成两个，然后接着对这两个列表做同样的操作。

巴特西

02python算法-二分法简介

最新文章

热门文章