【算法】【二分法】二分法详解

先给y总打一个广告。（我这种废物收不到钱）
本科时候就在打蓝桥杯玩玩算法，当时听朋友的一个刷题且涵盖教程的网站，ACWING。
www.acwing.com
里面好处是大部分基础算法都有，Y总的视频！ y总我的神！！！！。
非常适合萌新学学算法之类的。~~废物（比如说我）全都忘光了也能进去看看~~

前几天刷LeetCode100刚好有一个算法思路使用二分作为一个优化，发现自己对于二分理解不是很到位，所以就回去研究了一下，发现之前确实缺失太多。。。。
但还好看几个小时也能弄懂了。

但我刷别人教程，感觉写的还不是很明白？？索性自己记录一下。~~不然就可以Copy别人的了，可恶，没被我找到。~~

基础

二分基础非常好理解，算是作为一个intro部分。后面基本遇不到这么简单的环境感觉。

场景：给你一个单调递增的序列，让你找到其中的一个数。当然递增递减无所谓。但我们额外一个假设是所有数字在这个数组里面唯一。
好，这个就是一个二分的标准模板。
首先先明确一下我们的目标：我们用二分的目标是优化时间复杂度
假设说我现在不知道二分，那我肯定没啥办法，直接暴力循环一个一个看，那么这样子的时间复杂度就是O（N）
但如果使用二分的话，就能够直接将这个时间复杂度直接降到O(log n)

先理解一下算法思想：
这个场景式给定了一个具体的区间，首先我们可以先看一下区间的中点，那么这时候就有三种情况：

区间中点就是你要的target，这时候皆大欢喜，直接return。
区间中点比target小，那这时候一想，我区间中点都比我的target小，那么我的target一定在我的右边吧。这时候就可以把左边砍掉。
区间中点比target大，跟上面同理，右边就不用看了。

所以看2，3这两种情况，他都能将原本的区间砍半，然后变为原本区间的一半，那么就等价于我们最早的假设，在一个区间找一个数，只不过这个区间比原来少了一半。那不就递归了，可以写代码了。
也正是这个砍半，所以能够将原本时间复杂度降到log n

大致代码框架


func binarySearch(arr []int, al int, ar int, tar int) int {
	l, r := al, ar					// search的区间
	for l < r {
		mid := (l + r) >> 1
		if arr[mid] == tar {		// 根据条件，修改区间l,r
			return mid
		} else if arr[mid] > tar {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	return l
}

进阶

首先，先来参透一下二分的本质。

刚刚那个intro里面，目标其实是降低复杂度。但是为什么能够降低复杂度，他的核心是什么？实际上他的核心在于他能够直接将一半的区间都不需要考虑。那么为什么他能够让一半的区间都不需要考虑？
因为这里的MID实际上代表了他右边（左边）的一整个群体，只要这个MID不满足条件，那么他的另外一半一定不满足

所以二分本质不是单调，而在于二分类，只不过单调这个性质很容易就能够达到二分类的效果

基于这个逻辑，我就更希望让刚刚基础版本考虑三种情况降到只考虑两种情况。（实际上是我瞎说的，只不过现在算法里面大家都考虑两种情况）

怎么弄成只考虑两种情况？很简单，还是按照刚刚环境，第一个不是 == 那你把他随便归类到其中一个，把其中一个改为 <= 或者另外一个改为 >= 就完事了。

那我怎么找到这个target？还是一样找吧，因为他还是在你的目标区间里面吧。
但很有意思的是两种分法使得，二分法变成了两种现象。刚刚提及归类有两种方法吧，一种可以将他归为左边，一种将他归为右边。

所以就变成了查找某个区间的端点。而这个值要么是你的target，要么就是比你的target恰好大一点或者小一点
在这里插入图片描述
也就是寻找图中红色端点，或者图中绿色的端点。

而这里对应这个两个模板


func BL(arr [] int, sl int, sr int, tar int) int {
    l, r := sl, sr
    
    for l < r {
        mid := (l + r + 1) >> 1		// 必有加
        if arr[mid] <= tar {
            l = mid
        } else {
            r = mid - 1 	// 有减
        }
    }
    
    return l
}

func BR(arr [] int, sl int, sr int, tar int) int {
    l, r := sl, sr
    
    for l < r {
        mid := (l + r) >> 1
        if arr[mid] >= tar {
            r = mid
        } else {
            l = mid + 1 	
        }
    }
    
    return l
}

上面代码的BL就对应查找图中红色端点，BR就对应查找图中蓝色端点。

解释一下代码更好背代码。

先解释红色：（这里场景还是用刚才那个，也就是数组单调递增等等）

首先，你找红色，那就是把你的target并到左边那边，而这里面的左边也就可以认为是所有比target小或者等这一类。

其次我们都假设true会怎么样，false会怎么样。

true的话就说明我的这个mid落在了红色这个区间，但是我是希望能够找到更为接近的右端点把？所以这时候我就需要更新l 为我的mid。因为这个mid依旧符合这个红色区间条件，所以我并不能把他排除。需要让他进行下一步考虑。
false的话就说明这个mid落在了绿色这个区间，那肯定是错的。所以这时候就要让r改为mid-1

然后仔细看这里mid在算的时候，不是简单算中点，为什么？