二分查找!!再学不会就是瓜皮

2017-05-10  本文已影响0人  刘宇轩Freeman

首先想清楚!!二分查找分为四种(数组中包含重复元素)分别为

YES_LEFT   ----> 能找到且返回最左边的数的位置
YES_RIGHT ----> 能找到且返回最右边的数的位置
NO_LEFT     ----> 不能找到且返回左边与其接近的数的位置
NO_RIGHT  ----> 不能找到且返回右边与其接近的数的位置

例如下列数组:

2 3 4 4 4 6 6 6 6 7

YES_LEFT(4) -> 2 
YES_RIGHT(4) -> 4 
NO_LEFT(6) -> 4 
NO_RIGHT(6) -> 9

对于YES_LEFT或者NO_RIGHT

int bSearch(int begin, int end, int e)  
{  
    int mid;
    int  left = begin;
    int  right = end;  

    while(left <= right)  
    {   
        mid = (left + right) >> 1;  
        if(num[mid] >= e){
            right = mid - 1;  
        }else {
            left = mid + 1;
        }  
    }  
    return left;  
}  

对于YES_RIGHT或者NO_LEFT

 int bSearch(int begin, int end, int e)  
    {  
        int mid;
        int  left = begin;
        int  right = end;  

        while(left <= right)  
        {   
            mid = (left + right) >> 1;  
            if(num[mid] > e){
                right = mid - 1;  
            }else {
                left = mid + 1;
            }  
        }  
        return right;  
}  
上一篇下一篇

猜你喜欢

热点阅读