二分总结

一、二分查找

首先明确一下二分查找可以解决的问题， 二分查找可以解决预排序数组的查找问题。只要数组中包含T（即要查找的值），那么通过不断的缩小包含T的范围，最终就可以找到它。一开始，范围覆盖整个数组，将数组的中间项与T进行比较，可以排除一般的元素，范围缩小一半。就这样反复比较反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。对于包含N个元素的表，整个查找过程大约要经过logN次比较。

需要注意的是，二分查找是针对有序数组而言。

感觉没怎么可说的 。。

看代码吧

1.非递归的形式

int erf(int s[],int n,int key){
    int left = 1 , right = n ;//数组大小
    while(left <= right){
        int mid = (left +　right) / 2;
        //这里mid需要放在while内部，否则无法更新
        //也可以用 >> 1 代替
        //既可以提高效率，也可以防止溢出
        if(s[mid] < key) left = mid + 1;
        //数组中间的位置得数小于要查找的数，那么我们就在中间数的右区间找
        else if(s[mid] > key)
           right = mid - 1;
        //数组中间的位置得数大于要查找的数，那么我们就在中间数的左区间找
        else return mid;//中间数刚好是要查找的数字。
    }
    return -1;
}

2.递归形式

int erf(int s[],int left,int right,int key){
    int left = 1 , right = n ;
    while(left <= right){
        int mid = (left +　right) / 2;
        if(s[mid] == key)
           return mid;
        else if(s[mid] < key)
           return erf(s[] , mid + 1 , right , key);
        else
           return erf(s[] , left , mid - 1 , key);
    }
    return -1;
}

此外：大部分人喜欢在最开始就判断s[mid]与key相等，但是这样不太好，因为相等情况在大多状况下都是少数，写在开始的话，每次循环都需要判断一次相等，浪费时间。

二、二分答案

二分答案都有一个标志，比如题目中会给你，让你求最大值最小或者最小值最大之类的话。

前提：

1.答案区间的上下界确定，换句话说也就是答案在什么范围是知道的

2.可以比较容易的检验出某个答案的正确性，也就是给你一个值，你能比较容易的知道是否符合题目要求。

3.可行解满足区间单调性，即若x是可行解，则在答案区间内x+1（也可能是x-1）也可行。

第1种情况：求最小值最大

int erf(){
    int left = min_ans , right = max_ans;
    while(left < right){
        int mid = (left + right) / 2 ;
        if(check(mid))  left = mid;
        else right = mid - 1;
    }
    return left;
}

第二种情况：求最大值最小

int erf(){
    int left = min_ans , right = max_ans;
    while(left < right){
        int mid = (left + right) / 2 ;
        if(check(mid))  right = mid;
        else left = mid + 1;
    }
    return left;
}

关于二分边界问题，洛谷日报上有一篇帖子。

传送门