Range Checking Algorithm (check if there's a point in a given range)

Question: There is a stream of two different operations. One is placing a point on a single axis. The other is to check if there's a point in a given range. (see the image below)

 

1> Brute Force

1-1> For every range check, we can just go over all the points it includes. Time complexity for that would be O(R * N), where R is range and N is the number of range checks.

1-2> Or, we can just go over all the points and check the point is included in the range. Time complexity would be O(M * N), where M is the number of points.

 

2> Binary Search

If we put points in ascending order, then we can use binary search to solve the problem. Putting points in order would take O(M*logM).

Then, binary search to find out where both start and end of the range should be placed --> O(N*logM).

from bisect import bisect_left, bisect_right

points = [-1, 2, 7, 9, 13]

ranges = [(-2, 1), (2, 2), (3, 5), (10, 14)]

for s, e in ranges:
    i, j = bisect_left(points, s), bisect_right(points, e)
    if i != j:
        print('There\'s at least one point in the given range.')
    else:
        print('There\'s no point in the given range.')