algorithm - java - search sorted list of rectangles -

i have list of rectangles, created in usual way with:

list<rectangle> rects = new arraylist<>(); 

some rectangles added (all non-zero width , height). number of rectangles list contains can anywhere between 0 , 10,000, , typically between 4,000 , 6,000.

the list sorted ascending x-coordinate of rectangle origin, , ascending y-coordinate duplicate x-coordinates (though 2 or more rectangles same x-coordinate rare).

i've verified sorting being done correctly (i'm using collections.sort custom comparator).

i need method takes input 2 ints, x , y, , returns first rectangle found containing point (x,y), or null if no rectangle in list contains point.

public rectangle findcontainingrectangle(int x, int y) 

the naive method, give desired functionality, loop through list , call contains method on each rectangle, slow.

the list modified while program running, @ insignificant rate compared rate @ list needs searched, algorithm requires relatively slow initialization fine.

i've looked @ collections.binarysearch couldn't figure out how might used. don't have experience java if there's collection used list better suited type of search need, that's great (i have read documentation on things maps , sets didn't recognize advantage).

while maintaining sorted list, use binary search on 'x' coordinate find candidates of rectangles contain wanted 'x', , after which, use binary search on 'y' coordinate.

you should implement binary search yourself, can't see way can use collections.binarysearch method.

expected complexity: o(log n) n number of rectangles. (it's bit more because might have duplicates)

however ,to so, should keep array sorted while adding other instances, (sort after every insert).