华为OD机试解析：IP区间覆盖算法与C语言实现

1. 华为OD机试真题解析：IP定位与区间覆盖问题

这道来自华为OD机考的编程题，表面上是简单的区间查询问题，实则考察了数据结构选择、算法优化和工程思维的综合运用。题目要求我们根据给定的IP段与城市对应关系，快速查询任意IP所属城市——这正是现实中CDN调度、反欺诈系统等场景的核心需求。

IP地址本质上是32位无符号整数（IPv4），通常表示为点分十进制。例如192.168.1.1对应的整数值为：

code复制192*(256^3) + 168*(256^2) + 1*(256^1) + 1*(256^0) = 3232235777

这种转换是后续处理的基础，在C语言中可以通过位运算高效实现。

2. 核心解题思路与算法选择

2.1 暴力解法及其缺陷

最直观的做法是将所有IP段存储为数组，对每个查询IP线性遍历所有区间：

c复制for(int i=0; i<n; i++){
    if(ip >= ranges[i].start && ip <= ranges[i].end){
        return ranges[i].city;
    }
}

时间复杂度O(n) per query，当区间数量达到百万级时（实际业务常见），这种解法完全不可行。

2.2 区间覆盖问题的经典解法

高效解决方案需要预处理区间数据：

1. 排序+二分查找：将所有区间按起始IP排序，查询时用二分查找定位可能区间
2. 线段树：构建树结构加速区间查询
3. 前缀树(Trie)：特别适合IP这类有固定位宽的数据

实测表明，在华为OD的测试用例规模下（区间数≤1e5），排序+二分的方法在实现难度和性能间取得最佳平衡。

3. C语言实现详解

3.1 数据结构设计

c复制typedef struct {
    unsigned int start;
    unsigned int end;
    char city[32];
} IPRange;

IPRange ranges[MAX_N];
int range_count;

3.2 IP转换函数

c复制unsigned int ip_to_int(const char* ip) {
    unsigned a