二分法

不知道大家有没有玩过一个猜数字的游戏？玩家一给出一个区间和一个数字，由玩家二来猜这个数字，区间会随着玩家二猜的数字发生变化。

在不考虑表情变化或者别的影响因素时，玩家二要如何去猜这个数字呢？

下面我们要介绍的，就是这个游戏的万能解法----二分法，也叫做二分查找法

定义

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

过程

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

关键元素

  • 排好序的列表list

  • 左区间left

  • 右区间right

  • 中间点mid

  • 目标值target

性质

时间复杂度

二分查找的最优时间复杂度为 O(1)O(1)。

二分查找的平均时间复杂度和最坏时间复杂度均为O(logn)O(logn) 。因为在二分搜索过程中，算法每次都把查询的区间减半，所以对于一个长度为nn的数组，至多会进行O(logn)O(logn)次查找。

空间复杂度

迭代版本的二分查找的空间复杂度为O(1)O(1) 。

递归（无尾调用消除）版本的二分查找的空间复杂度为O(logn)O(logn) 。

Tips

二分法的演变过程如下图所示

h1

通过不断的修正区间，达到找目标值的目的。

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def Bisection(tar):
    weight=[1<<i for i in range(1,10)]
    print("Weight is ",weight)
    l,r=0,len(weight)-1
    
    while l<=r:
        # 确定中心点
        mid=(r-l)//2+l
        # 修改边界
        if weight[mid]==tar:
            # 找到了中心点
            return mid
        if weight[mid]<tar:
            # 目标值在右边
            # 此时需要把区间往右移动
            l=mid+1
        else:
            r=mid-1
    return -1

我们来看看输出情况

1
2
3
4
5
print(Bisection(512))
print(Bisection(127))
print(Bisection(128))
print(Bisection(0))
print(Bisection(513))
1
2
3
4
5
6
7
8
9
10
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
8
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
-1
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
6
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
-1
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
-1

可以发现，目标值都被正确的输出了，而不在范围内的值，则是以-1进行输出。

二分插入

向右边插入

这个问题的关键在于，当tar==mid的时候，我们让左区间往右走。于是，当出现相同值的时候，插入位置被修正为右边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def Bisection(tar):
    weight=[1<<i for i in range(1,10)]
    print("Weight is ",weight)
    l,r=0,len(weight)-1

    while l<=r:
        # 确定中心点
        mid=(r-l)//2+l
        # 修改边界
        if weight[mid]<=tar:
            # 此时需要把左区间往右移动
            l=mid+1
        else:
            r=mid-1
    return l
1
2
3
4
5
6
7
8
9
10
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
9
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
6
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
7
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
0
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
9

诶，我们发现，512的插入位置在9号，128的插入位置在7号。

向左插入

同理啦，我们只需要在tar==n[mid]的时候，把右区间往左移，从而实现拿到左端点的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def Bisection(tar):
    weight=[1<<i for i in range(1,10)]
    print("Weight is ",weight)
    l,r=0,len(weight)-1


    while l<=r:
        # 确定中心点
        mid=(r-l)//2+l
        # 修改边界
        if weight[mid]>=tar:
            # 此时需要把右区间往左移动
            r=mid-1
        else:
            l=mid+1
    return l
1
2
3
4
5
6
7
8
9
10
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
8
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
6
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
6
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
0
Weight is  [2, 4, 8, 16, 32, 64, 128, 256, 512]
9

可以看到，512被插入到了8号位，513则被插入到了9号位。