美文网首页
二分查找!!再学不会就是瓜皮

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

作者: 刘宇轩Freeman | 来源:发表于2017-05-10 20:18 被阅读0次

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

    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;  
    }  
    

    相关文章

      网友评论

          本文标题:二分查找!!再学不会就是瓜皮

          本文链接:https://www.haomeiwen.com/subject/hjagtxtx.html