Find the interval in a list of non-overlapping intervals that contains a value. Example of geoip table lookup: given an IP find a location. Motivated by: https://dev.maxmind.com/geoip/geoip2/geoip2-city-country-csv-databases/

find_interval.py

# Problem: given this data (xs) and value (x) find it's mapped str value ('SG', ...)
# Tuple format: (interval_start_inclusive, interval_end_inclusive, searched_value) 
db = [(8123, 9888, 'SG'), (1, 1000, 'US'), (1001, 5045, 'CA')]

# Solution: sort once
db_sorted = sorted(db, key=lambda x: x[0])

# Implement binary search (for practice purposes):
def binary_search(x, xs):
    if not xs:
        return None
    else:
        mid = len(xs) // 2
        mid_val = xs[mid]
        start = mid_val[0]
        end = mid_val[1]
        if start <= x <= end:
            return mid_val[2]
        elif x < start:
            return binary_search(x, xs[:mid])
        else:
            return binary_search(x, xs[mid + 1:])

# Tests:
print(binary_search(2, db_sorted))  # US

print(binary_search(9888, db_sorted))  # SG

print(binary_search(9889, db_sorted))  # None

print(binary_search(0, db_sorted))  # None

print(binary_search(1000, db_sorted))  # US

# Discuss cons and pros of this approach. Propose other alternatives.