二分法小总结

最近刷了许多的二分算法题，从简单到困难，有一些心得体会，做个记录以便以后复习。

首先一个感悟就是，二分法究竟在干嘛，它的算法核心是什么？

是while循环么？

是二分概念么？

那二分的概念又是在干嘛呢？

第一点：二分在干嘛

其实，个人觉得，二分的核心在于决定抛弃哪一部分的数据以达到decrease and conquer的目的。而如何去做这个抛弃的决定，就要看数据本身的特点。

例如，标准二分，给的数据就是有序序列，那么你就要将nums[mid]和target比较，然后决定抛弃前面还是后面。

当给定的数据变了，例如经典的旋转数组，即把有序数组割开，然后拼接，例如 1 2 3 4 5 6，从 2 隔开变成 3 4 5 6 1 2

这样的数据的结构，用二分思想的时候，怎么去决定抛弃哪一部分呢？这个时候就需要根据数据本身去确定，这里就要分几种情况去讨论。

第二点：敏锐的察觉二分的概念

当我们看到有序数组查找的时候，就很容易想到二分！咱们用二分！但有时候二分会嵌入到某些问题中，比如前缀和中的查找，前缀全是正整数的话，那么前缀和一定是递增的，递增即有序，有序中的查找你就会想到二分。

所以二分熟练应用应该是内化为自己的思想的，应该存在于自己解决问题的方法路径当中。

当我们去刷这些算法的时候，我想更多的不是去记住每一个问题对应的代码，而是养成一个解决问题的思维，运用各种数据结构和基本的算法思路去解决复杂的问题，数据结构和算法应该是画笔，而不是画好的画。