Given an N-by-N array a of N^{2} 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

## No comments:

Post a Comment