You are given an mxn grid, in which each entry stores a positive integer. All numbers...

 

Transcribed Image Text:

You are given an mxn grid, in which each entry stores a positive integer. All numbers are distinct. Your task is to find one entry which is larger than all its neighbors. (The neighbors of entry [i, j] are [i - 1, j], [i+1,j], [i, j-1], and [i, j+1]; note that an entry in a corner has 2 neighbors, and an entry on an edge (but not corner) has 3 neighbors.) 1. Suppose that m = 1. Design an algorithm for this task. Your algorithm should run in O(logn) time. (Note that in this case each of two boundary entries has 1 neighbors, while each of the other entries has 2 neighbors.) Prove that your algorithm is correct. 2. Suppose that m=n. Design an algorithm for this task. Your algorithm should run in O(n) time. You are given an mxn grid, in which each entry stores a positive integer. All numbers are distinct. Your task is to find one entry which is larger than all its neighbors. (The neighbors of entry [i, j] are [i - 1, j], [i+1,j], [i, j-1], and [i, j+1]; note that an entry in a corner has 2 neighbors, and an entry on an edge (but not corner) has 3 neighbors.) 1. Suppose that m = 1. Design an algorithm for this task. Your algorithm should run in O(logn) time. (Note that in this case each of two boundary entries has 1 neighbors, while each of the other entries has 2 neighbors.) Prove that your algorithm is correct. 2. Suppose that m=n. Design an algorithm for this task. Your algorithm should run in O(n) time.