find x in non-overlapping ranges

range:
    min
    max

// pre-condition: ranges are sorted and are not overlapping
// O(logn)
range find(x, ranges):
    if ranges == null:
        throw
    if ranges.isEmpty():
        return nullRange
    return findInner(ranges)

// O(nlogn)
sort(ranges):
    ranges = ranges.sort(x => x.min)

// ranges need to be sorted
// O(n)
validate(ranges):
    if ranges.isEmpty():
        return
    prevRange = ranges[0]
    for i = 1, i < ranges.count(), i++:
        range = ranges[i]
        if !(prevRange.max < range.min):
            throw
        prevRange = range

// O(logn)
findInner(ranges):
    start = 0
    end = ranges.count() -1
    while start <= end:
        mid = start + (end-start)/2
        range = ranges[mid]
        if x < range.min:
            end = mid -1
        else if x > range.max:
            start = mid +1
        else:
            return range
    return nullRange