这道题的目的是找到矩阵中的极小值。
采取的方法:
1. 找到mid列中的最小值的元素k
2. 分布取k左边和右边的元素,如果此时k比它们小,则为结果,否则答案就在小于k的元素所在的位置的那一块
很容易想到可以用二分法去实现
那么为什么2是正确的呢?
这里先假设k左边的元素比k小,该元素记为l,如果l恰好是极小值,那么很高兴我们找到了要的元素。那如果存在一个元素e正好在l的旁边比l小呢?
由于k是mid列的最小的元素,所以mid列中所有位置的元素都大于等于k,而l<k,所以mid列中所有位置的元素都大于l。而e<l,那么mid列中所有位置的元素都大于e。这就保证了e一定小于mid列的所有元素。
由此可得,mid-1列的最小值一定小于mid列的所有元素。
由此类推,要么找到了极小值,要么一直到第0列,由于第0列的最小值小于第1列的所有值,那第0列的最小值就是我们要找的元素。
故分布取k左边和右边的元素,如果此时k比它们小,则为结果,否则答案就在小于k的元素所在的位置的那一块。
而这个性质保证了二分法的正确性
赞