PreviousNext
Coding/Searching and sorting

Range cardinality estimate

Write codeMedium22 minSnowflake and Oracle style

Your task

A B-tree index stores integer keys in sorted order (duplicates allowed). Implement a range-scan cardinality estimate that returns the exact count of index entries with key in the inclusive range [lo, hi]. The keys are given already sorted ascending. You must run in O(log n), do NOT linearly scan. If lo > hi, return 0. Up to 200000 keys.

Examples

index_range_count(keys: list[int], lo: int, hi: int) -> int
Example 1
Inputindex_range_count([1, 3, 3, 5, 8, 8, 8, 12], 3, 8)
Output6