#saddleback-search

Saddleback Search

Saddleback Search Saddleback search finds a target in a matrix where each row and each column is sorted in nondecreasing order. It walks through the matrix along a monotone path, eliminating one row or one column at each step. Problem Given a matrix $A$ of size $n \times m$ such that: $$ A[i][j] \le A[i][j+1] \quad \text{(rows sorted)} $$ $$ A[i][j] \le A[i+1][j] \quad \text{(columns sorted)} $$ find a position...