才发现自己不会二分法

╰+攻爆jí腚メ 2023-02-27 05:41 138阅读 0赞

今天看到一道二分法的题，别人花了500行左右讲解，二分法这么简单的需要这么讲解吗？现实很打脸！！！  
题目：在一组有序数组中，查找数值X，找到就返回数值对应的序号，未找到就返回-1。  
这是楼主第一遍写的：

int findNum_error_1(const vector<int>& vec,int num)
    {
        
        int start = 0;
        int end = vec.size() - 1;
        while (start < end)
        {
        
            int mid = start + (end - start) / 2;
            if (vec.at(mid) == num)
            {
        
                return mid;
            }
            else if (vec.at(mid) > num)
            {
        
                end = mid;
            }
            else if (vec.at(mid) < num)
            {
        
                start = mid ;
            }
        }
        return -1;
    }

列出一个（1，2，3，4，5，6）数组，在其中查找7，如下图，最后进入了死循环  
![在这里插入图片描述][20200716135509687.png]然后楼主很蠢的改写了如下代码

int findNum_error(const vector<int>& vec,int num)
    {
        
        int start = 0;
        int end = vec.size() - 1;
        while (start < end)
        {
        
            int mid = (start + ceil((end - start) * 1.0 / 2));
            if (vec.at(mid) == num)
            {
        
                return mid;
            }
            else if (vec.at(mid) > num)
            {
        
                end = mid;
            }
            else if (vec.at(mid) < num)
            {
        
                start = mid ;
            }
    
    
        }
        return -1;
    }

完美，7找到了，返回了-1，解决了死循环，接下来查找1，又死循环了  
![在这里插入图片描述][20200716135712190.png]  
啪啪打脸后，还是觉得去学习下大神总结的  
1、左边界二分法  
左边界二分法的关键是：  
① end = vec.size();  
② while (start < end)；因为end = vec.size(),end=比最大序号+1，但受到 (start < end)限制，不会出现越界  
③ start = mid + 1;

int findNum_left(const vector<int>& vec,int num)
    {
        
        int start = 0;
        int end = vec.size();
        while (start < end)
        {
        
            int mid = (end + start) / 2;
            if (vec.at(mid) == num)
            {
        
                return mid;
            }
            else if (vec.at(mid) > num)
            {
        
                end = mid;
            }
            else if (vec.at(mid) < num)
            {
        
                start = mid + 1;
            }
        }
        return -1;
    }

2、右边界二分法  
右边界二分法的关键是  
① end = vec.size();  
② while (start < end)  
③ start = mid + 1; if (vec.at(mid) == num) start = mid + 1;

int findNum_right(const vector<int>& vec,int num)
    {
        
        int start = 0;
        int end = vec.size();
        while (start < end)
        {
        
            int mid = (end + start) / 2;
            if (vec.at(mid) == num)
            {
        
                start =  mid + 1;
            }
            else if (vec.at(mid) > num)
            {
        
                end = mid; 
            }
            else if (vec.at(mid) < num)
            {
        
                start = mid + 1;
            }
        }
        return (start >= 1) && vec.at(start - 1) == num ? (start - 1) : -1;
    }

3、全封闭二分法  
全封闭二分法就是以上两种的统一

int findNum_normal(const vector<int>& vec,int num)
    {
        
        int start = 0;
        int end = vec.size() - 1;
        while (start <= end)
        {
        
            int mid = start + (end - start) / 2;
            if (vec.at(mid) == num)
            {
        
                end =  mid - 1;
            }
            else if (vec.at(mid) > num)
            {
        
                end = mid - 1;
            }
            else if (vec.at(mid) < num)
            {
        
                start = mid + 1;
            }
        }
        if (start >= vec.size() || vec.at(start) != num)
        {
        
            return -1;
        }
        return start;
    }

[20200716135509687.png]: /images/20230209/5c871324f9b74830a91ef27e5b3e8e18.png
[20200716135712190.png]: /images/20230209/45926c6e9df84ee28abf4ba59edf2ac8.png