Find a local minimum in a 2-D array

Given an N-by-N array a of N² distinct integers, design an O(N) algorithm to find a local minimum: an pair of indices i and j such that:

• a[i][j] < a[i+1][j]
• a[i][j] < a[i-1][j]
• a[i][j] < a[i][j+1]
• a[i][j] < a[i][j-1]

Find the minimum entry in row N/2, say a[N/2][j]. check all entries in its column, if we get smaller entry in column, then recur in the row where smaller column entry belongs.

eg. For array below, N=5:

1  12  3   1  -23  
7   9  8   5   6
4   5  6  -1  77
7   0  35 -2  -4
6  83  1   7  -6

Step 1: The middle row is [4 5 6 -1 77]. ie. row number 3.

Step 2: Minimum entry in current row is -1.


Step 3: Minimum entry in that column would be -2. ( Row 4)


Continue with steps 2-3 till we get the local min.


Iteration 2:


Step 2: Minimum entry in row 4 is –4.


Step 3: Minimum entry in that column would be –23 ( Row 1)


Iteration 3:


Step 2: Minimum entry in row 1 is –23.


Step 3: Minimum entry in that column is –23


Local Minimum would be -23