LeetcodeT74搜索二维矩阵

详细解释了二分查找在不同条件下该如何设定缩减边界，以及总结了几种模板。

二分查找的三种类型

写一个找准确值的都会写，但是每次稍作变换，比如“找比x大的最小的数”，或者如T34一样有重复值的左边界，等等，我就晕了orz。

看了一个b站视频，感觉自己仿佛懂了，因此在这里记录下来。

首先，无论如何，二分查找有两个必须要满足的条件：

• 每次都要缩减搜索区域
• 每次缩减不能排除掉答案

在以上条件的基础下，up主将不同类型的题目整理出如下的三大模板。

1.找准确值

这是最简单的情况，大家都会。

• 循环条件 ： start <= end

• 缩减空间 ： start = mid +1

  ​ end = mid -1

2.找模糊值

这就有好多情况了，题目里也经常遇到，比如找比target大的最小数这种，还有某个数的左边界右边界什么的，但依然注意这两件事就可以。

• 循环条件 ： start < end

• 缩减空间 ： start = mid

  ​ end = mid - 1

  ​ 或者： start = mid + 1

  ​ end = mid

那么这两种缩减空间应该在如何选择呢？举个例子，例如，想要寻找2的左边界，数组可能为两种情况：

1	1	2	==2==	2	6	7
1	1	1	==2==	2	6	7

查找到2后，这个2可能就是左边界，也可能它的左边还有2，因此要继续搜索左边的区域、并且不能排除掉这个2。

因此，此时的缩减空间应该为end = mid。也就对应的前文第二种缩减空间。

相应的，如果此时mid值小于2，那么mid值一定不会为答案，直接在右边查找就可以，缩减空间是start = mid + 1。

其他的时候也都依靠这种思路分析，发现比以前清楚了好多。

这里还有一个小问题，为什么这里的判断条件是start<end，而不是找准确值时的start<=end了呢？

这是因为，缩减时会有start = mid 或者 end = mid的情况，如果数组只有一个值，缩减也没用，会陷入死循环。

3.通用型

还有一种情况是，要找到最接近target的值。

• 循环条件 ： start < end - 1

• 缩减空间 ： start = mid

  ​ end = mid

  此时，start和end相邻时就可以结束了，因此缩减只要=mid就可以了。

  这种方法的优点就在于可以留下两个值，最后可以比较一下哪个更接近target。

mid的写法

mid的写法也有两点需要注意，第一是注意溢出的问题，第二是当数组长度为偶数时，指针会在中间偏左的数上，在某些条件下会死循环。有时应该让它在中间偏右的数上，也需要考虑一下。

可以参照的写法如下：

mid = start + (end - start)/2;
mid = start + (end - start+1)/2;

Leetcode T74

学好了思路就开始做题。首先我想要在第一列中，找出小于等于target的数里，最大的那一个。

那么缩减空间应该是什么样的呢？

如果mid大于target，答案肯定在左侧，不会包括mid，也就是end=mid-1 ；

如果mid小于target，答案可能是mid，也可能还在右边，因此start = mid 。

接下来考虑mid的问题，由于缩减时可能start = mid，当只有两个值的时候 ，左边的是start也是mid，会死循环，因此注意我们要让mid落在中间偏右的那个位置上。

找到答案所在行的二分搜索代码如下：

 static int BinarySearchRow(int[][] matrix, int target)
    {
        int start = 0;
        int end = matrix.length-1;
        while (start < end)
        {
            int mid = start + (end - start + 1) / 2;
            if (target < matrix[mid][0])
                end = mid - 1;
            else if (target > matrix[mid][0])
                start = mid ;
            else if (target == matrix[mid][0])
                return mid;
        }
        return start;
    }

找到答案的所在行之后，在当前行查找出答案，由于不会有重复值的情况，只要用最基础的准确查找就可以了。

找到指定行后，查找出所在位置的代码如下：

 static int BinnarySearch(int[] arr,int target)
    {
        int start = 0;
        int end = arr.length-1;
        while(start<=end)
        {
            int mid = start + (end - start) / 2;
            if (arr[mid]==target)
                return mid;
            else if(arr[mid]<target)
                start=mid + 1;
            else if(arr[mid]>target)
                end = mid - 1;
        }
        return -1;
    }