You can search a 2d space efficiently with quadtrees. Essentially it's like a binary search of a 1d space expanded to 2 dimensions. For each point you're searching it should take log(n) time to search for which hexagon it goes to if you first build a quadtree out of the n hexagons that tesselate your search area.