vlambda博客
学习文章列表

算法刷题注意事项

算法刷题更要注重质量，最好对做过的每一道题都要分析背后的基本原理，然后写出准确的代码。

如果当时没有想出好的解法，是因为什么？

经过多次调试才过的题目，出错的地方又是在哪里？

看答案才明白的和自己写出来，是完全不同的层次，完全不同的境界，几乎没有可比性。

如果以上这些问题不注意，过段时间再做这道题，还是可能不会，还是可能要看答案，反反复复，不管作多少遍，算法的技能始终进步不大。

所以，算法刷题一定要多思考，多总结，一定要注重质量！

今天讨论，二分查找

二分查找注意事项

二分查找表面看似很简单，就是对解空间的不断二分，直至逼近解并返回。但是实操起来，却绝非这么简单。

1. 要首先分析出对谁折半，有些问题显而易见，如有序数组查某个数的位置，因为索引值越大，元素值就越大，所以对索引范围折半。但是，有些问题对谁折半，就会复杂一些，需要分析分析。对谁折半的原则：寻找一个关系 ，如果自变量 变大，因变量 就变大(小)，是一个线性正或负相关关系，则 便可作为折半的对象。

2. 确定好对谁折半后，二分查找的折半条件 一般也就确定下来 。或者步骤1和步骤2是要相结合构思出来的，而不是串行的步骤。

3. 确定好这些后，编写代码仍然需要注意，等号取和不取时，不同的的low,high写法。

4. 再有注意 while 循环条件，low < high，low <= high，这些都会影响二分的写法。

5. 到底是返回 low ，还是 high，这要根据题目、步骤3和4的写法来确定。

终级一战

如今我们刷题来到Day99，这是作业题：

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

 

示例：

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。

链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix

这道题的最高效解法是二分查找。

以下两种写法都是准确无误的：

写法1：

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n = len(matrix)
        low,high=matrix[0][0],matrix[-1][-1]
        while low <= high:
            mid = (low+high)//2
            low_count = 0
            i,j =n-1,0
            while i >=0 and j <=n-1:
                if matrix[i][j] < mid:
                    low_count += i+1
                    j += 1
                else:
                    i -= 1
            if low_count < k:
                low = mid + 1
            else:
                high = mid - 1
        return high

写法2：

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n = len(matrix)
        low,high=matrix[0][0],matrix[-1][-1]
        while low < high:
            mid = (low+high)//2
            low_count = 0
            i,j =n-1,0
            while i >=0 and j <=n-1:
                if matrix[i][j] <= mid:
                    low_count += i+1
                    j += 1
                else:
                    i -= 1
            if low_count < k:
                low = mid + 1
            else:
                high = mid

        return high

提出两个思考问题

借助这道题，我们深入理解二分查找。请仔细体会以上两种写法的差异，对于我们深入理解二分逼近式的锁定解，具有重要意义。

请回答以下两个问题：

1 matrix[i][j] < mid  和 matrix[i][j] <= mid，这两种求比mid小的元素个数的写法，对外层书写二分条件有什么影响？为什么？

2 二分查找返回的解一定是矩阵中的元素吗？这也是此题最需要被解释的问题之一。

比如，若

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 20]
],
k = 8

返回结果14，15，16 都满足是矩阵的第8小元素，但它们都不是矩阵中的元素，以上两种二分查找的解法是如何保证不返回此类解。

欢迎写出你的答案：