Finding nearest point in an efficient way

Solution 1:

Use a quad-tree for 2D http://en.wikipedia.org/wiki/Quadtree

Solution 2:

Voronoi diagram is designed specifically for finding nearest point very fast. Although it's quite a pain to implement, you might find some existing library/implementation.

There's also an option to of repeatedly dividing plane in squares, thus building some kind of tree where each non-leaf node has 4 children (top-right square, bottom-right square, etc.). Then, of four squares you find the one your point is in and proceed with it recursively. Often this yields point close enough, so you may eliminate the need to check other squares.
But it's easy to create a 'counter-example' for this strategy which will result in linear time.

But there's not much you can do with your sorted array to speed up the process. You'll need a special data structure.

edit
Second structure is called Quadtree, thanks to VGE for providing the name.

Solution 3:

For efficient nearest neighbour search you need to use a spatial partitioning scheme, for example a kd-tree.