data structures - Binary search over 2d array to find a local maximum? What's wrong with this algorithm? -


this classic finding local maximum (just one) in matrix.

my algorithm is:

  • choose number in center of matrix.
  • check if number peak. if yes, return.
  • if not, check numbers left , right. if 1 of them greater our current number, choose half of matrix. if both greater, can choose either half.

  • repeat numbers top , bottom. leave 1 quadrant of matrix continue checking.

since binary search n x n matrix has n^2 elements, should take o(log(n^2)) = o(2*log(n)) = o(log(n))

i'm pretty sure not correct, mistake?

this algorithm isn't guaranteed find local maximum. consider example case need follow winding path through matrix of ascending values peak. if path crosses , forth between quadrants algorithm not find it.

13  1  1  1  1 12  1  1  1  1 11  1  1  2  3 10  1  1  1  4  9  8  7  6  5 

or, here's simpler example:

3  1  1  1  1 1  1  1  1  1 1  1  1  1  1 1  1  1  1  1 1  1  1  1  1 

you start in middle, how find '3'? algorithm doesn't describe when faced horizontal plane.


Comments

Popular posts from this blog

resizing Telegram inline keyboard -

command line - How can a Python program background itself? -

php - "cURL error 28: Resolving timed out" on Wordpress on Azure App Service on Linux -