【二分】二分查找算法
转载于:https://blog.csdn.net/jacob_007/article/details/52601847?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
[二分查找算法]
算法中经常用到二分查找算法，比如最常规的应用就是在一个有序数组中找特定的数，但是如何写出一个完整准确的二分法呢，边界条件如何判断，到底是等于还是不等？可能会困恼大家，比如说查找第一个等于5的数，那又在如何查找呢？查找最后一个等于5的数，又该如何改变？
这里有一个公式，可以解决所有这类的问题，它分为四步走：
1. 判定条件为start+1小于end，start=0, end=size-1
2. mid=start+((end-start)>>1)
3. 如果data[mid]满足条件直接返回，如果满足条件的数据在mid的右边则将start=mid，如果满足条件的数据在mid左边则将end=mid
4. 根据条件再次判定start，end两个元素是否满足条件
其实整个过程就不断缩小范围的过程，最后一步就是将整个数组的范围缩小到start end两个元素而已。
这里第3步有一个小的窍门就是不管什么情况下都应该单独判data[mid]大于等于和小于的情况，而不应该合并，因为会比较容易出错。
下面以求在有序数组中求最后一个等于特定元素的位置为例
class Solution {public:/*** @param A an integer array sorted in ascending order* @param target an integer* @return an integer*/int lastPosition( vector< int>& A, int target) {if( A.empty() ){return -1;}int Start = 0;int End = A.size() - 1;while(Start+1 < End){auto Mid = Start + ( (End-Start) >> 1 );if( A[Mid] == target){相等的情况只可能出现的Mid的右边Start = Mid;} else if( A[Mid] < target){Start = Mid;} else{End = Mid;}}if( A[End] == target){因为是求最后一个等于target的元素位置，所以对于一个两个元素的数组，当然是先判断end了return End;} else if( A[Start] == target){return Start;} else{return -1;}}};
非常简单吧。
典型题目，求sqrt
class Solution {public:/*** @param x: An integer* @return: The sqrt of x*/int sqrt(int x) {if(0 == x){return 0;}long Start = 0;long End = x;while(Start+1 < End){auto Mid = Start + ( (End-Start) >> 1);long MidSquare = Mid * Mid;if(MidSquare == x){return Mid;} else if(MidSquare < x){Start = Mid;} else{End = Mid;}}if(End*End < x){return End;} else{return Start;}}};
还有一种典型的题目就是在一个sorted array中寻找一个数字，但是这个sorted array可能旋转过的
二分排序算法
二分排序算法思想是分治，将大的问题简化成为小的问题，所有小的问题全部解决了，整个问题就解决了。
二分排序的期望复杂度是O(nlgn)，最差情况是O(n^2)
二分排序中最重要的是partition函数，直接写不容易写对，下面直接给出模板
int pivot = nums[begin];int left = begin;int right = end;while (left < right){while(left < right && nums[right] > pivot) {right--;}nums[left] = nums[ right] ;while(left < right && nums[left] <= pivot) {left++;}nums[right] = nums[ left] ;}nums[left] = pivot;
return left;最后left和right会相遇，相遇位置存放的就是pivot，接下来就是继续处理左右两个子集典型应用有，求第k大数从大到小的采用partition方法，如果返回的pivot位置正好是k-1，则直接返回，如果比k-1小，则第k-1个数肯定在pivot的右边，也就是找k-1-pivot大的数，如果比k-1大，则在pivot的左边找第k-1大的数。
这种算法叫做quickselect，期望的复杂度是O(n)，最差是O(n^2)
另外一种场景就是在一个数据流中求中位数或者第k大数
数据流的意思就是不能一下子load出所有的数据，只能一个一个处理，这种场景就需要建立两个PQ，一个是最小堆，一个是最大堆，前面k个数为最小堆，后面len-k个数为最大堆，当有新的数进来的时候先判断这个数是应该放在左边还是右边，然后直接插入，再重新调整，保证左边的数据个数为k个就可以，所以每次压入一个新数，左边的堆顶元素则为所求。这也是采用partition的思想来解决问题。
这里有一种变形就是如果是window的第k大数，则需要用hashheap，因为window移动的时候需要增加一个元素同时再删除一个元素，hash就可以最快的找到元素从heap中删除。
ps：在求前k个数或者第k大数时优先考虑quickselect，然后就是PQ是一个比较好的策略，算法的复杂度为nlgk
二分合并
二分排序是将大问题分解成为小问题，当所有小问题全部解决了，那最后的结果也就出来了，二分合并则是先将问题分割成为小问题，解决每个小问题，然后将小问题的结果合并得到最后的结果。
最典型的问题就是合并n个链表，n个有序链表，如何合并成为一个有序链表？这道题目有两种解法：
1. 将n个有序序列的第一个元素压入到PQ中，然后从PQ每次取出最大值，同时将最大值的下一个节点再次压入PQ中，依次将所有节点合并。这个算法的复杂度为mlgn，总共有m个节点
2. 每次两两合并，最终得到一个结果，这是典型的合并排序，这个算法复杂度为mlgn
小结
二分法在实际的项目中运用还是非常多的，算是基本算法，其中心思想是分治，它除了在数组中使用较多，另外一个应用的场景就是二叉树的问题。