关于c++二分算法的详解

在这个狗题频出的时代，暴力算法是必不可少的工具。今天，bo~~~~~ki~将以蒟蒻视角，为您精彩将算法之，二分之谜。手动狗头

不开玩笑啊，算法确实是很重要的一点，不会的话只能用暴力，硬做。如果不会，那么时间超限阵容欢迎您的到来！其实DFS也是半斤八两。所以说我准备出一个专栏，专门讲各种我会的算法，当然是以蒟蒻的视角，因为本人就是个蒟蒻。而且今天，我还有一个朋友。Jerry，给大家打个招呼。Hello！行了，我们进入正题吧。

1.二分是什么

学二分之前我们必须要弄懂啥是二分，你不能稀里糊涂的直接上代码，那是蒟蒻行为好像我也是个蒟蒻。二分其实就是暴力的优化，从字面意思就可以理解，二分就是每次折半，举个例子：

1 3 4 5 7 8 9 10 11 12 15

在这个有序序列中，我们要找15。暴力怎么找？从第一个遍历到最后一个，通过11次循环后找到了十五。那二分呢？锁定中间值8，8小于15，因为我们这个序列是升序，所以往右边找。确定右边子序列的中间值11，11小于15，再往右。找到右子序列的右子序列的中间值(如果是偶数的话用靠前那个)12，12小于15，往右，15等于15，只用了4次查找就找到了，这就是二分的思路。

2.二分的作用

那二分有什么用呢？我说过，二分就是暴力的优化，那肯定就是用来优化暴力的啊废话！不是废话，二分确实是用来优化暴力的还是废话。你闭嘴。二分的时间复杂度可以列为O(logN)，可以说是非常低了，就是代码写的多上5，6行而已，你说用哪个吧我就要用暴力，你要咋。不是让你闭嘴了吗!?

砰砰，啪啪，叮当，哐 w(ﾟДﾟ)w

刚才出了点小插曲啊，没事儿，我们继续。这个大家能用二分就尽量不要用暴力，容易时间超限啊。

3.二分查找的代码

人之初，性本善，不写代码是好汉。我不是好汉，我要写代码应该是怕没有阅读量吧。又皮痒了是不？再乱说小心我抽你！

这个二分的代码他分三种，第一种，也是最适合装逼的，用递归

#include<bits/stdc++.h>
using namespace std;
int a[101],n,key;
void half(int l,int r){
	int mid=(l+r)>>1;
	if(l<=r){
		if(key<a[mid]){
			half(l,mid-1);
		}else if(key>a[mid]){
			half(mid+1,r);
		}else{
			cout << mid;
			return;
		}
	}
	cout << 0;
	return;
}
int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	cin >> key;
	if(a[1]>key||a[n]<key){
		cout << 0;
	}else{
		half(1,n);
	}
	return 0;
}

第二种，用一个函数(我这边就只给函数了，主函数你们自己写，这样可以训练脑子和代码能力)

其实就是懒得写

你过来！看我不抽死你！

int binary_search(int left,int right,int key){
    int ret=-1;
    int mid;
    while(left<=right){
        mid=left+((right-left)>>1);
        if(arr[mid]<key)
            left=mid+1;
        else if(arr[mid]>key)
            right=mid-1;
        else{
            ret=mid;
            break;
        }
    }
    return ret;
}

第三种，用循环，这个直接把函数里面的内容复制进去就行了，我这里就不演示了。

4.总结

这个二分是一种非常好的算法，后面做大数据量运算的时候很有用，非常值得掌握，还有，这个我用了一个小细节。

mid=left+((right-left)>>1);

这可以让你代码运算速度稍微提升那么一点，小数据量没啥，等数据大了差距就拉开了更多是装逼，你哪有那么好心去科普啊。 

好了，今天的内容就到这儿了，希望对你们有帮助，拜拜，我去收拾Jerry去了

Jerry有种你别跑！！！

哦，对了忘了骗求赞了，制作不易，点个赞再走吧！

Jerry你还敢胡扯！？