Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

Sorted Matrix Search


Given an M * N matrix in which each row and each column is sorted in ascending order, write a method to find an element.

how to solve


The above link is very easy understanding.

We begin with the upper right corner. Instead of traversing diagonally each step, we traverse one step to the left or bottom. Essentially, each step we are able to eliminate either a row or a column. This algorithm runs in O(n+m).