对二分法比较浅显的理解(暑假刚学,肤浅勿喷)

· · 个人记录

一.为什么不用暴力而用二分法:

其实二分法也是暴力的一种,只不过更体面而已.
其实,选用二分法的原因在于它的时间复杂度实在是小(O(nlogn))如果我们去 暴力搜索,大部分情况下是O(n^2)的时间复杂度,二分法一下就帮我们砍掉了很多的 时间.

二.二分的基本用处:

用来充当暴力

其实确实是用来充当暴力的

 二分答案,二分查找之类的

三.注意事项:

1.二分答案最关键的在于它的判断函数,bool在什么情况下返回1,什么情况下返回0.

2.在主函数里面有一些小细节,比如左边界和右边界在满足什么情况下,不再二分.这些情况在不同的题目里面不一样,我暑假就被这些可恶的情况坑了好久

3.虽然二分通常和贪心结合在一起,贪心一定一定要经过严谨的数学推断!!!如果是推断失败,不能贪心,那就放弃吧(因为我多半做不出动态规划+二分来,那至少是蓝色级别的题目)