二分查找算法及变种的编码实现

Question

二分查找问题是比较经典而且面试中常考的问题，实现起来还是容易出问题，能够过关的不多，请问实现一个二分查找有哪些容易错的地方（比如小数的处理、数据相加的范围等）？

变种一：（多个公司的面试都喜欢出）如果有序序列发生偏移即把序列的后面一部分截取放在前面，比如：

11 13 1 2 4 7 9

此时再给定一个数，查找其在序列中是否存在（返回其位置），请问如何实现？

变种二：同上题描述，找出序列中最小元素位置。

变种三：给定任意一个序列，找出其中的一个谷/峰，谷的定义为两边的数均大于某个数。

请问面试中还遇到过哪些二分查找的变种？

Answer 1

1. 对于输入的所有单词，使用排序算法使得所有单词按照字典序排列，然后用BS算法找到给定的单词的下标。
2. 在给定的字符串序列中（按照字典序排列好的）存在一些空串，请你找出给定字符串的位置，不在里面返回 -1.
3. 在一个排序好的数组中，有一些元素是重复的。 我们写一个函数，对给定的数，我们返回这个数出现的次数。
4. 在行列排序的矩阵中里面需找某个元素，例如如下输入：

1 5 7 10
2 6 8 15
4 9 11 16
12 13 19 21

输入满足按行来看，是递增排序，按列也是递增排序，现在要是否存在某个元素。

Answer 2

说下第三个
要用三分法
记 l , m , r 分别为左端点、中端点、右端点。f(x) 为在x点的函数的值
取 lm = (l + m ） / 2 , rm = (m + r) / 2 ;

然后 比较 f(lm)　f(rm)的关系 ， 相应的更新l , m , r 就可以了

Answer 3

个人总结的几个变种（只是为了描述算法本身，为了简单不考虑越界等等异常情况），欢迎补充。

/*  
    二分查找的前提是数组有序
    二分查找的时间复杂度：O（lgn）
    以下列出二分查找的三种动机：
    1、查找满足条件的关键字的位置
    2、查找满足条件的最小位置
    3、查找满足条件的最大位置
    找不到返回-1,找到了则返回位置
*/

//动机1(原始模型)：查找满足条件的关键字的位置
int BinarySearch(int *a,int l,int r)
{
    int m;
    while(l<=r)
    {
        m=(l+r)/2;
        if(a[m]==key)
            return m;
        if(a[m]>key)
            r=m-1;
        else
            l=m+1;
    }
    return-1;
}

//动机2：找满足条件的最小位置
int BinarySearch(int *a,int l,int r)
{
    int m,ans=-1;
    while(l<=r)
    {
        m=(l+r)/2;
        //满足条件
        if(ok())
            ans=m,r=m-1;
        else
            l=m+1;
    }
    return ans;
}

//动机3：找满足条件的最大位置
int BinarySearch(int *a,int l,int r)
{
    int m,ans=-1;
    while(l<=r)
    {
        m=(l+r)/2;
        //满足条件
        if(ok())
            ans=m,l=m+1;
        else
            r=m-1;
    }
    return ans;
}

//动机2、3十分相似,举一种常用情况：找小于等于某数的最大位置
int BinarySearch(int *a,int l,int r,int key)
{
    int m,ans=-1;
    while(l<=r)
    {
        m=(l+r)/2;
        if(key>=a[m])
            ans=m,l=m+1;
        else
            r=m-1;
    }
    return ans;
}

//变型1：找满足条件的最小数(double)
double BinarySearch(double l,double r)
{
    double m,ans;
    //保留n位小数就让精度为n+1位,比如要求保留3位小数就让精度为4位
    while(r-l>=0.0001)
    {
        m=(l+r)*0.5;
        if(ok())
            ans=m,r=m;
        else
            l=m;
    }
    return ans;
}