Question

二分法是什么意思

Answer 1

其实就是一种通过不断的排除不可能的东西,来最终找到需要的东西的一种方法.所以可以理解成排除法.
之所以叫二分,是因为每次排除都把所有的情况分成"可能"和"不可能"两种,然后抛弃所有"不可能"的情况.
最正统的二分法中,是每次排除都可以排除掉一半的情况,这样子的寻找效率是很高的.
比如要在1-100的数字中询问出某一个特定的数字,我可以先问,这个数字是否大于50?这样无论是或者不是,我都可以排除掉一半的数字(50之前的被排除,或者50之后的被排除).假如回答不是,接着我可以问是否大于25?,又可以排除掉一半.这样下去,很快就会排除剩下一个数字.即是要找的那个.
要理解这种方法为什么这么快需要用一点数学计算,很显然最理想的二分法是每次把情况除以2,而逐个检查的方法是把情况减1,这个排除的速度比较只要稍微计算一下就可以有认识.
另外就是二分法不一定真的是平均二分,对于不平均的二分法,最极端的情况下,每次可能只能排除一种情况,这样就和逐个排查没有区别了.这叫做二分法的退化,是使用二分法的时候需要想办法避免的.

Answer 2