There's this thing called a BSP tree which just uses a plane instead of a line as in the case above. There ya go, binary search.