昆明hph网站建设网站建设服务费合同

一.二分

1.二分查找

我们来看这样一道题：

有一个保证有序的数组a，它的长度为n。现在我们需要知道这个序列是否含有x。
数据范围：保证n<=1e9

我们看到这道题之后，第一时间想到的就是暴力枚举了，可是我们发现直接枚举会超时。所以我们只能使用一种n logn时间复杂度的算法。
那么能满足n logn时间复杂度的算法，二分查找是首选项。

二分查找怎么找？

二分查找，俗称折半查找法。
折半查找法，顾名思义，每次将查找范围缩小，来达到优化时间的目的。
我们可以设序列a={1，10，25，30，101，234}，l为查找的左边界（搜索起点），r为查找的右边界（搜索终点），要查找它是否包含的数是4。
那么搜索起点就是1，终点就是n（a的长度）。
我们一定会用循环，可是，用哪种循环？条件是什么？
很明显，有条件才循环，所以用while循环
由于左边界在往右搜，右边界在往左搜，所以条件是l<r
原理：
左边最大的都小于了这个数，故不可能这个数在左边存在，同样，右边最小的都大于了这个数，故不可能这个数在右边存在。
如果最后搜索完了却依然没有找到，就输出No；
核心代码（模板）：

l=1,r=n;
while(l<=r)
{mid=(l+r)/2;if(a[mid]>m[i]){r=mid-1;}else if(a[mid]<m[i]){l=mid+1;}else{cout<<"Yes"<<endl;return 0;}
}
if(l>r)
{cout<<"NO"<<endl;
}

2.二分答案

刚才我们已经学了二分查找，那么二分答案也就没有太难了。
二分答案指的是给定了答案的范围，来二分查找最小的可能中最大的情况或最大的可能中最小的情况。

二分查找&二分答案练习题目【二分答案可作为挑战题】

练习必做题1，难度普及-
练习必做题2，难度普及-
挑战题1
挑战题2