s********0
发帖数: 51 | 1 是关于有序数组的搜索的，第一题是一维有序数组的搜索，用二分法很快就写出来了。
第二题是二维的有序数组，就是一个二维数组，其行和列都是有序的，比如：
1， 8， 15， 22， 25，32
3， 12，18， 28， 36，50
15， 25，34， 60， 64，90
60， 78，79， 80， 91，100
这样，每一行和每一列都是有序的，但是下一行/列不一定比上一行/列的都大。请问大
家，这种情况下如何搜索呢？复杂度是多少呢？谢谢！ |
c********6
发帖数: 33 | 2 看左下角的数字
如果target比它大往右移
比他小往上移 |
s********0
发帖数: 51 | 3 谢谢你！ 好像确实可以work的，能否给稍微讲解一下原理呢？另外，这样的话复杂度
应该是O(m+n)吧？有没有类似log（n）的算法呢？
【在 c********6 的大作中提到】
: 看左下角的数字
: 如果target比它大往右移
: 比他小往上移
|
C********e
发帖数: 492 | 4 沿着对角线A(i,i) 做类似二分查找，可以O(n)
【在 s********0 的大作中提到】
: 谢谢你！ 好像确实可以work的，能否给稍微讲解一下原理呢？另外，这样的话复杂度
: 应该是O(m+n)吧？有没有类似log（n）的算法呢？
|
c********6
发帖数: 33 | 5 原理是当target小于60的话，那么60这一行肯定不会有target了，所有数都比60大
target大于60的话那这一列就不用看了，因为所有数都比60小
log方法不太清楚，好像可以分成四块去二分，操作比较麻烦就是了
【在 s********0 的大作中提到】
: 谢谢你！ 好像确实可以work的，能否给稍微讲解一下原理呢？另外，这样的话复杂度
: 应该是O(m+n)吧？有没有类似log（n）的算法呢？
|
f*******w
发帖数: 1243 | |
G*********e
发帖数: 56 | 7 Young tablet。
算法书上有。
【在 s********0 的大作中提到】
: 是关于有序数组的搜索的，第一题是一维有序数组的搜索，用二分法很快就写出来了。
: 第二题是二维的有序数组，就是一个二维数组，其行和列都是有序的，比如：
: 1， 8， 15， 22， 25，32
: 3， 12，18， 28， 36，50
: 15， 25，34， 60， 64，90
: 60， 78，79， 80， 91，100
: 这样，每一行和每一列都是有序的，但是下一行/列不一定比上一行/列的都大。请问大
: 家，这种情况下如何搜索呢？复杂度是多少呢？谢谢！
|
z******t
发帖数: 59 | 8 的第8个例题。
这个题目通常有两个解法：
1、在对角线上二分查找。在对角线上找到比指定数字小的最大数，然后用这个数把二
维数组分成4个子数组。目标数字只有可能出现在刚才找到数组的右上子数组或者左下
子数组。接着在这两个子数组中递归查找。
这个思路的代码实现稍微有点复杂，在面试过程中不容易一次性写对。
2、每次拿数组右上角的数字和目标数字比较。如果相等，找到了。如果比目标数字大
，去掉最右边的一列；如果比目标数字小，去掉做上面的一行。接着用同样的思路，在
剩下的数组中继续拿右上角的数字和目标数字比较。
这个思路一旦把思路想清楚，写代码容易很多。这是面试过程中推荐的解法。 |
