NC105 二分查找法

作者: goto2091

二分查找(一)

二分查找看似简单,但是有很多的细节要注意。

题目是牛客NC105,找到有序数组中第一个大于或者等于所查找的数字。

初步写了如下的代码:

class Solution {
public:
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型vector 有序数组
     * @return int整型
     */
    int upper_bound_(int n, int v, vector<int>& a) {
        // write code here
        int mid=0;
        int left=0;
        int right=n-1;
        while(left < right)
        {

            //mid = left+(right-left)/2;
            mid = (left+right)/2;
            if(a[mid] > v){
                if(a[mid-1]<v) return mid;
                else{
                    right = mid-1;
                }

                left = mid+1;
            }else if(a[mid] == v)
            {
                while(a[mid] == v){
                    mid--;
                }
                return mid+1;//这里必须是mid+1?
            }
        }
            return n+1;
    }
};

运行之后发现测试用例不能完全通过,这段代码有什么问题?

首先是mid = left + (right-left)/2, 这和mid = (left+right)/2相比,有什么区别?

实际测试的时候,没有区别,但是一旦left和right都很大的时候,则有可能会造成数组越界。

因此,使用(right-left)/2可以很大程度避免两个很大的数相加导致数组越界的情况发生。

其次是把right=mid写成了right=mid-1。为什么?

因为a[mid]>v的情况下,a[mid]是符合题目要求的大于所查找数的,所以,right=mid,而不是right=mid-1。也就是说,没有把它排除。

代码还有bug,

while(a[mid] == v)
{
    mid--;
}
return mid+1;

把return mid+1改为了return mid+2,因为输出是按1而不是按0开始的。

的解题思路是,如果是大于v,则判断其左侧的位置是否小于v,如果小于则是第一个,如果等于v,则不断向左移动,直到找到小于v的位置。

标准题解:

标准题解把a[mid]>=v放到一起作为判断条件。这是因为既然是大于等于,则a[mid]>=v都是符合要求的,只要判断是不是第一次即可。

什么是第一次呢? 那就是mid左边的那个数如果是小于v的,则mid就是符合要求的。二分查找的本质,是left在等于right之前,不断查找符合条件的位置。
mid发现的位置是中间位置而不是'第一次'出现的位置。因为大于等于所找的值,这本身就是符合要求的条件,二分查找找的就是符合某条件的位置,不断地通过二分查找直到找到。

因此 a[mid]>=v可以写在一起。

最后经过优化的代码:

int upper_bound_(int n, int v, vector<int>& a) {
        // write code here
        int mid=0;
        int left=0;
        int right=n-1;
        while(left < right)
        {

            mid = left+(right-left)/2;//为什么要这样写Mid?
            if(a[mid] > v){
                if( mid == 0|| a[mid-1]<v) return mid+1;
                else{
                    right = mid;
                }
                left = mid+1;
            }else if(a[mid] == v)
            {
                if(a[mid-1]<v)
                return mid+1;
                else right = mid;
            }
        }
            return n+1;
    }

如果是left <=right呢?修改之后仍不会影响结果。

做完该题后,再看leetcode 704

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        int left = 0;
        int right = len-1;
        int mid = 0;
        while(left < right)//如果只有一个元素会如何呢?
        {
            mid = left + (right-left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else if(nums[mid] < target)
            {
                left = mid + 1;
            }
        }
        return -1;
    }
};

这段代码无法通过全部的测试用例,比如在测试元素只有一个的数组的时候报错了,因此要怎么办?

最好是用while(left<=right),这样就避免了一个元素时不进入循环的情况了。

继续趁热打铁,看leetcode 74题,搜索二维矩阵。 获取二维数组的行和列

行数 = sizeof(array)/sizeof(array[0])
列数 = sizeof(array[0])/sizeof(array[0][0])

行数计算方法就是用二维数组的整个size除以第一行的size

列数计算方法就是第一行除以每个元素的size.

求vector二维数组的行数,直接就是size()方法。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //只要先按照第一列进行二分查找,找到第一个大于等于的位置,然后该位置的
        //上一个数组就可能存在一个目标值,在在数组中继续二分查找。
        //行数
        //int m = sizeof(matrix)/sizeof(matrix[0]);
        int m = matrix.size();//直接就是行数
        int up = 0;
        int down = m-1;
        int mid1=0;
        while(up <= down)
        {
            mid1 = up+(down-up)/2;
            if(matrix[mid1][0] == target){
                return true;
                if(matrix[mid1-1][0] < target){//上一行中必然存在,mid1-1行可能存在
                    break;
                    down = mid1 -1 ;
                }
                up = mid1 + 1;
            }
        }
        int n = matrix[0].size();
        int left = 0;
        int right = n-1;
        int mid2 = 0;
        while(left <= right)
        {
            mid2 = left+(right-left)/2;
            if(matrix[mid1-1][mid2] == target){
                return true;
            }else if(matrix[mid1-1][mid2] > target)
            {
                right = mid2-1;
            }else if(matrix[mid1-1][mid2] < target)
            {
                left = mid2+1;
            }
        }

        return false;
    }
};

以上代码有什么错误?

没有考虑到空参数的问题,会出现'runtime error: reference binding to null pointer of type'提示。

如果是[[]] , 二维数组的特殊情形, 完全空,只有一行一列,多行一列,一行多列。这四种情况,都要在运行的时候考虑到。

因此,最稳妥的方式就是把二维数组转化为一维数组。但是一维数组有没有最大长度? 有,vector是有最大长度的。https://blog.csdn.net/iceboy314159/article/details/80329979

但是在本题中足够。

标准题解:

也不需要先将二维放入一维徒增空间复杂度,而是直接把二维数组当成一维数组。
a[mid]转换就是b[mid/n][mid % n],为什么? 第k个数是在二维数组种的位置便是[k / n][k % n]

这里的k包括了从0位置开始的记录。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //转化为一维数组,但是要考虑到长度问题。

        int m = matrix.size();
        int n = matrix[0].size();

        if( m == 0 || n == 0) return false;
        int left = 0;
        int right = m*n-1;
        int mid = 0;
        while(left <= right)
        {
            mid = left+(right-left)/2;
            int tmp = matrix[mid/n][mid%n];
            if(tmp > target){
                right = mid - 1;
            }else if(tmp < target)
            {
                left = mid + 1;
            }else 
                return true;
        }
        return false;
    }
};

这一块代码为什么还有问题? 输入了[]之后,还是会有错误?

因为输入了[]之后,其中这不是二维数组,所以行数为0,而行数为0的情况下判断martix[0].size()就是不可能的。

所以应该先判断行数是否存在,存在后再计算列数。

改代码为:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //转化为一维数组,但是要考虑到长度问题。

        int m = matrix.size();
        if(m == 0) return false;
        int n = matrix[0].size();

        if( n == 0) return false;
        int left = 0;
        int right = m*n-1;
        int mid = 0;
        while(left <= right)
        {
            mid = left+(right-left)/2;
            int tmp = matrix[mid/n][mid%n];
            if(tmp > target){
                right = mid - 1;
            }else if(tmp < target)
            {
                left = mid + 1;
            }else 
                return true;
        }
        return false;
    }
};

当然,这样做的时间复杂度是MN,而空间复杂度为1.有没有更好的方法呢? 那就是前面提到的先判断在哪一行,再判断是该行的哪一列。

加上了对二维数组的判空后,第一种做法仍然会报错,这是由于还有1行1列,1行多列的情况存在,这种情况下,mid-1就会出现负值,导致出错。

这样的话,判断条件非常多,所以不选择在第一列找,而是在最后一列找,在最后一列找到第一次大于target的,则找到的mid就是可能存在该数的行。 二分查找中遇到Mid==0该怎么办 mid为0的情况,比如前一个mid为1,但是还是不满足条件,然后再次除以2,从而mid==0,此时left和right也相等,则不需要再查找,而是直接跳出。

还有一种情况,就是只有一个元素的数组。总之,mid为0表示之后不需要再次计算。

原文创作:goto2091

原文链接:https://www.cnblogs.com/goto2091/p/13757967.html

更多推荐

更多
这里什么都没有

近期文章

更多
文章目录

    推荐作者

    更多