BinarySearch and its variant

7月 19 2014

今天看到一道有点需要借助二分的一道leetcode题，于是想起当时编程之美(Beauty Of Programming)还有一系列课后题还没搞定，加之之前不经意见问了下高富帅思路，突然有了一些感觉，于是把这些题目都做一做，都是BinarySearch的一些变形。

今天博客看到比我这个变种还多的大神，实在是膜拜啊，http://blog.csdn.net/luckyxiaoqiang/article/details/8937978

正常BinarySearch
这个是基本的二分，之前还阅读编程珠玑(Progamming Pearls)证明过,注意low<=high, 后面就是正常的high=mid-1, low<high, 后面就是high=mid, 那些proof感觉不实用，难道写了代码，还花那么多时间去找一个assertion去proof它的correctness么？
因此我总结了一个方法，就是看是否每个分支是否会至少减小search size 1个大小(除掉return)，如果每次都减，一定不会死循环，因为size大小固定，<0就exit loop了。关键就是mid=(low+high)/2这个语句了，因为奇数除会丢精度，
由于bit right shift的原因，所以这个是是否reduce size的关键。这个，我猜也是为啥46年就提出了BS的思想，但是62年才有第一个正确的algorithm吧。

find max i, arr[i]=x
这个是受高富帅点播的，如果找到相等了，low=mid, 包含当前元素向高区间找，然后如果区间size=1就返回这个mid，否则low=mid.但是一个样例测发现死循环了，后来分析发现了当时size=2,low+1=high, mid=(low+high)/2=low, 所以low=mid赋值就原地不动
，size不变，于是死循环了，所以两个element时候，特别处理，直接看a[low] a[high] 就行了，如果a[high]==x 就是high了，否则就是low了。

代码如下：

int BS_MaxIEqualX(int A[], int n, int x)
{
    int low=0, high=n-1;
    while(low<=high)
    {
        if(low==high) return A[low]==x ? low : -1;
        if(low+1==high) return A[high]==x ? high : (A[low]==x ? low : -1);//two ele not process, may nonterminal loop
        int mid=(low+high)/2;
        if(A[mid] < x) low=mid+1;
        else if(A[mid] > x) high=mid-1;
        else
            low=mid;
    }
    return -1;
}

上面的代码似乎有问题，没有拿OJ测，今天看到一道找找相等元素在数组中上下界的问题，然后重新写了一下代码，代码通过了OJ，应该是正确的。这里面是找等于元素的上下界，因此1,2两问的代码嵌在里面，
而且逻辑更加清楚，Knuth说过，过早优化是万恶的源头，确实如此，因为一开始你未必分析清楚逻辑，不要想着怎么把条件合并，就像印度人代码，虽然冗长但是正确，不容易有bug。这一系列都得益于高富帅
的点播，不愧是华科一哥啊，代码思路至少已经比较清晰了，只是还没证明正确性，未必正确，但是对AC至少有一定信心了。

    vector<int> searchRange(int a[], int n, int target) {
        int lowequal=-1,highequal=-1;

        int low=0,high=n-1;
        while(low<=high)
        {
            int mid=low+(high-low)/2;
            if(target==a[mid])
            {
                if(low==high)
                {
                    lowequal=low;break;
                }
                else
                {
                    high=mid;
                }
            }
            else if(target<a[mid])
            {
                high=mid-1;
            }
            else
                low=mid+1;
        }

        low=0,high=n-1;
        while(low<=high)
        {
            int mid=low+(high-low)/2;
            if(a[mid]==target)
            {
                if(high==low)//avoid unlimited loop
                {
                    highequal=low;//high
                    break;
                }
                else if(high==low+1)//avoid unlimited loop
                {
                    if(a[high]==target)
                    {
                        highequal=high;
                        break;
                    }
                    else
                    {
                        highequal=low;
                        break;
                    }
                }
                else//at least three elements
                {
                    low=mid;
                }
            }
            else if(a[mid]<target)
            {
                low=mid+1;
            }
            else if(a[mid]>target)
            {
                high=mid-1;
            }

        }

        vector<int> range;
        range.push_back(lowequal);
        range.push_back(highequal);
        return range;
    }

find min i, arr[i]=x
这个和上面类似，但是其实比那个还简单一些，因为两个元素的时候，mid=(low+high)/2=low, high=mid使得size-1了，不会死循环。这个也是和上面的微妙差别

int BS_MinIEqualX(int A[], int n, int x)
{

 int low=0, high=n-1;
 while(low<=high)
 {
     if(low==high) return A[low]==x ? low : -1;
     int mid=(low+high)/2;
     if(A[mid] < x) low=mid+1;
     else if(A[mid] > x) high=mid-1;
     else high=mid;
 }
 return -1;

}

find max i arr[i]<x
和上面的区别在于分支修改不同，这里x<=a[mid] 说明mid及以上的都不可能是解，于是修改a[mid]<x 里面，解在这里面，一个元素直接return mid，两个元素注意unlimited loop了，x<=a[high], high不可能了，所以return low，否则就return high了

int BS_MaxILowerX(int A[], int n, int x)
{
```
 int low=0, high=n-1;
 while(low<=high)
 {
     if(low==high) return A[low]<x ? low : -1;
     if(low+1==high) return A[high] < x ? high : (A[low] < x ? low : -1);
     int mid=(low+high)/2;
     if(A[mid] < x) low=mid;
     else high=mid-1;
 }//do not exit loop
```
}

另外这道算法是否可以直接改写基本的BS呢，我手动模拟感觉就是找不到，循环退出时的high，但是不知道怎么证明的. 感觉如果x一定是找不到的，这个写法似乎是对的，如果找得到就不知道了。如果对的话，同理可得下面的代码

int BS_MaxiLowerX(int *a, int n, int x)
{
```
 int low=0,high=n-1;
 while(low<=high)
 {
     int mid=low+(high-low)/2;
     if(a[mid]<x)
     {
         low=mid+1;
     }
     else if(x<a[mid])
         high=mid-1;
     else
         return mid;
 }
 return high;
```
}

find min i arr[i]>x
同上，只是不需要特殊处理了，因为high=mid 必reduce search size

int BS_MinIHigherX(int A[], int n, int x)
{

 int low=0, high=n-1;
 while(low<=high)
 {
     if(low==high) return A[low]>x ? low : -1;
     //if(low+1==high) return A[high] < x ? high : (A[low] < x ? low : -1);
     int mid=(low+high)/2;
     if(A[mid] <= x) low=mid+1;
     else high=mid;
 }//do not exit loop

}

Posted by richard爱闹 - 7月 19 2014
如需转载，请注明：本文来自 Richard

留言