Saddleback Search | Algorithms Notes

Saddleback Search | Algorithms Notes

M is an n * n integer matrix in which the entries of each row are in increasing order (reading left to right) and the entries in each column are in increasing order (reading top to bottom). Give an efficient algorithm to find the position of an integer x in M, or determine that x is not there. Tell how many comparisons of x with matrix entries your algorithm does in the worst case.

Solution:

If M[i][j] > x, then M[i][k] ≠ x for all j ≤ k ≤ n and M[k][j] ≠ x for all 1 ≤ k ≤ i. Likewise, M[i][j] < x reveals corresponding information. Hence, let i = 1 and j = n initially, if M[i][j] = x, report it; if M[i][j] > x or M[i][j] < x, compare x with M[i][j-1] or M[i+1][j] respectively in the next iteration, unless j-1 < 1 or i+1 > n, which implies that x is not in M. Since the increments and decrements of i and j are O(n), the total running time is O(n).

For m time n sorted matrix, finding an element can be done in O(m lg (n / m)) [1], where m is the number of rows and n is the number of columns, m ≤ n. First do binary in the middle row M[mid] to find the index i, such that M[mid][i] < x < M[mid][i+1]. Then, the submatrix in the top-left of M[mid][i] and the submatrix in the bottom-right of M[mid][i+1] cannot have x. We can recursively solve the problem in the remaining two submatrices.

Note: This technique can be generalized to 3D [2]

[1] Richard S. Bird, "Improving Saddleback Search: A Lesson in Algorithm Design," Mathematics of Program Construction Lecture Notes in Computer Science Volume 4014, 2006, pp 82-89

[2] N Linial, M Saks, "Searching ordered structures," Journal of Algorithms Volume 6, Issue 1, March 1985, Pages 86–103

解法：

如果 M[i][j]大於x，那M[i][k]不等於x對於所有j ≤ k ≤ n且M[k][j]不等於x對於所有1 ≤ k ≤ i。相同的，如果M[i][j]小於x也能得到類似的資訊。因此，令i為1、j為n，如果M[i][j]等於x，那就找到了解答。如果M[i][j]大於或是小於x，在下一輪中就要拿x和M[i][j-1]或M[i+1][j]來比較，除非j-1小於1或是i+1大於n，這代表x不在M中。因為i和j頂多只能被遞增或是遞減O(n)次，所以時間複雜度為O(n)。

Read full article from Saddleback Search | Algorithms Notes