使用二分查找判断某个数在某个区间中--如何判断某个IP地址所属的地区-阿里云开发者社区

一，问题描述

给定100万个区间对，假设这些区间对是互不重叠的，如何判断某个数属于哪个区间？

首先需要对区间的特性进行分析：区间是不是有序的？有序是指：后一个区间的起始位置要大于前一个区间的终点位置。
如：[0,10]，[15,30]，[47，89]，[90，100]…..就是有序的区间
[15,30]，[0,10]，[90，100]，[47，89]……就是无序的区间

其次，区间是不是连续的？连续是指：后一个区间的起始位置比前一个区间的终点位置大1，连续的区间一定是有序的。
如：[0，10]，[11，30]，[31，89]，[90，100]……

下面先来考虑连续区间的查找，即：假设有100万个区间，给定一个数，判断这个数位于100万个区间中的哪一个，一个实际的应用实例就是：给定一个IP地址，如何判断该IP地址所属的地区？比如：[startIp1, endIp1]---》广东深圳、[startIp2，endIp2]---》广东广州、[startIp3, endIp3]---》四川成都……要查找某个IP所在的地区，先要判断出该IP在哪个区间内，再取出该区间对应的地区信息。

二，一种实现方式
首先将“字符串类型的IP地址”转换成长整型，这是为了方便比较大小。比如：“70.112.108.147” 转换之后变成1181772947，转换结果是唯一的。具体原理可参考：这篇文章

简要转换思路是：一个IP地址32bit，一共有四部分，每部分都是一个十进制的整数。首先将每部分转换成二进制，然后再对每部分移位，最终将每部分的移位结果相加，得到一个长整型的整数。如下图所示（图片来源）：

经过上面的IP到长整型的转换后，就可以使用一个长整型数组long[]来保存所有的IP区间对了。给定一个待查找的字符串类型的IP地址，先将之转换成长整型，然后再使用二分查找算法查找long[]即可。
由于我们不仅仅是找出某个IP在哪个区间段内，而是根据该IP所在的区间段获得该区间段对应的地区信息。由于IP区间保存在long[]数组中，因此使用一个ArrayList保存地区信息，通过数组下标的方式将long[] 与ArrayList 元素一一对应起来。

三，算法的正确性证明
对于二分查找而言，循环while(low <= high)最后执行的一步是 low==high，假设待查找的数位于某个区间内，那么最后一次while循环时，low 和 high 要么同时指向该区间的左边界，要么同时指向该区间的右边界。假设待查找的数为15，如下图所示：

若low和high同时指向左边界（比如13），mid = (low+high)/2 = low = high，根据前面假设，这个数位于区间内，那么 arr[mid] < 这个数，low指针更新为mid+1，从而 low > high，跳出循环。而high指针则刚好指向这个数所在区间的左边界。

若low和high同时指向右边界（比如17），mid = (low+high)/2 = low = high，根据前面假设，这个数位于区间内，那么 arr[mid] > 这个数，high 指针更新为 mid-1，从而low>high，跳出循环，此时high指针也刚好指向该区间的左边界。因此，最终 high 指针的位置就是这个数所在区间的左边界。

由于每个区间有两个位置（起始位置和结束位置），每个区间对应一个地区信息，因此：Long[]数组的长度是ArrayList长度的两倍。那么二分查找中返回的 high 指针的位置除以2，就是该区间对应的地址信息了（ArrayList.get(high / 2)）

当然了，若待查找的数，刚好位于区间的边界上（起始位置/结束位置），那就代表二分查找命中，直接 return mid 返回查找结果了。

特殊情况：若待查找的数比所有区间中的最小的数还小，由于long[]是有序的，那么最后一次while(low<=high)循环一定是 low 和 high 同时指向 long[]中索引为0的位置，然后high = mid -1 变成 -1（即high>0）
若待查找的数比所有区间中的最大的数还要大，由于long[]是有序的，那么最后一次while(low<=high)循环一定是 low 和 high 同时指向 long[]中索引为long[]数组的arr.length-1的位置，然后low = mid +1 变成arr.length（即low > arr.length-1）

四，区间不连续的情况

区间不连续，只有序时，同样可使用二分查找，可能出现的情况与（三）中分析的一样，只是这里还有一种情况：待查找的数不在任何一个区间内，而是在两个相邻的区间之间。比如查找26，但它不在任何一个区间内。如下图所示：

这种情况，跳出while循环的条件还是 low > high，但是此时 low 指向一个区间，而high指向另一个区间，可以根据 low 和 high 指向不同的区间来判断26不在任何一个区间中。

若 low / 2 == high / 2 则 low 和 high 指向相同的区间，若 low /2 != high/2 则，low 和 high指向不同的区间。

如下图所示：

而在（三）中，while循环结束后，low 和 high 还是指向同一个区间（具体而言，就是high 总是指向区间A的起始位置，而low指向区间A的终点位置）。

五，代码实现

假设所有的IP信息存储在文件ipJson.conf文件中，大约有100万条，其中一条数据的格式如下：（自己构造的一条示例数据而已）：该IP区间是[3085210000，3085219875]，对应的地区是：”中国/四川/成都“

{"begin_int_ip":"3085210000","end_int_ip":"3085219875","country":"中国","province":"四川","city":"成都"}

使用fastjson将数据解析出来，关于fastJson解析数据，可参考：FastJson使用示例，并初始化long[]数组和 ArrayList数组：代码如下：

 1     private int parse() {
 2         JSONReader jsonReader = null;
 3         int index = 0;
 4         try {
 5             jsonReader = new JSONReader(new FileReader(new File(FILE_PATH)));
 6         } catch (FileNotFoundException e) {
 7         }
 8         int recordNum = 0;
 9         jsonReader.startArray();// ---> [
10 
11         while (jsonReader.hasNext()) {
12             IpInfo ipInfo = jsonReader.readObject(IpInfo.class);// 根据 java bean 来解析
13             ipSegments[index++] = ipInfo.getBegin_int_ip();
14             ipSegments[index++] = ipInfo.getEnd_int_ip();
15             ipRegions.add(new Address(ipInfo.getCountry(), ipInfo.getProvince(), ipInfo.getCity()));
16             recordNum++;
17         }
18         jsonReader.endArray();// ---> ]
19         jsonReader.close();
20         return recordNum;
21     }

将字符串类型的IP地址转换成长整型的方法如下：

1     private static long toSmallLongFromIpAddress(String strIp) {
2         long[] ip = new long[4];
3         String[] ipSegments = strIp.split("\\.");
4         for(int i = 0; i < 4; i++) {
5             ip[i] = Long.parseLong(ipSegments[i]);
6         }
7         return (ip[0] << 24) + (ip[1] << 16) + (ip[2] << 8) + ip[3];
8     }

连续区间的二分查找算法如下：

    private int binarySearch(long[] arr, long searchNumber) {
        if(arr == null || arr.length == 0)
            throw new IllegalArgumentException("初始化失败...");
        return binarySearch(arr, 0, arr.length-1, searchNumber);
    }
    private int binarySearch(long[] arr, int low, int high, long searchNumber) {
        int mid;
        System.out.println("arr len:" + arr.length);
        while(low <= high)
        {
            mid = (low + high) / 2;
            if(arr[mid] > searchNumber)
                high = mid - 1;
            else if(arr[mid] < searchNumber)
                low = mid + 1;
            else
                return mid;//待查找的数刚好在区间边界上
        }
        
        System.out.println("low=" + low + ", high=" + high);
        
        //low > high
        if(low > arr.length-1 || high < 0)//待查找的数比最大的数还要大,或者比最小的数还要小
            return -1;//not found
        
        return high;
    }