登录以参加训练计划

二分

二分法，你思考过这些问题吗？

如何优雅的处理边界条件？

一定要数据有序时才能使用二分法吗？

如何优雅的证明二分法的时间复杂度是O(logn)？

什么是二分法？

​ ​二分法​(Bisection method)，即一分为二的的方法。对于在区间[a,b]上连续不断且满足f(a)*f(b)<0的函数y=f(x),通过不断地把函数f(x)的零点所在区间二等分，使区间两个端点逐步逼近零点，进而得到零点的近似值的方法。

​ ​说人话​：把答案所在的区间逐渐缩小，直到区间内只有答案。

比如猜数字游戏：给定一个1--100之间的正整数，让你猜。猜的过程中给出大小判断的提醒，问怎么才能快速地猜出来？ 最快的方法是：每次猜区间的中间点的数字。如果中间点大于给定数字，下次就猜前半部分的中间点数字；如果中间点数字小于给定数字，下次就猜后半部分的中间点数字。