一，问题描述

给定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的终点位置)。

-------------------------------------------------------

重新更新：2019.5.29

看了下JDK的源码：java.util.Arrays#binarySearch0(T[], int, int, T, java.util.Comparator super T>)

其实JDK里面Arrays类已经实现了二分查找，如果查找命中，则返回数组下标；若未命中，则返回一个负数，(负数+1)再乘以(-1) 就是待插入的下标(有序)。

因此，直接使用Arrays类的binarySearch方法就能完美实现 区间 查找。

示例如下：

给定有序区间：[2,5]  [8,9]  [9,16]  [19,25]

因为区间对放入数组，因此，数组的长度肯定是个偶数。因此，当数组中有重复的元素时，二分查找重复元素时，若查找命中，返回的下标是 "数组下标小的那个"。比如查找元素9，查找命中，返回的index=3。

将之放入数组，得到：[2,5,8,9,9,16,19,25]

假设查找2：

二分查找命中，返回元素2的数组下标 index=0，0是偶数，说明：元素2在区间(index,index+1)区间上，即区间[2,5]

假设查找9：

二分查找命中，返回元素9的数组下标index=3，3是奇数，说明：元素9在区间(index-1,index)上，即区间[8,9]，当然了，对于这种特殊的情形，视具体的需求处理。

假设查找10：

二分查找不命中，返回 index=-6，(-6+1)*-1=5，说明元素10可插入在数组下标为5的位置处。由于5是个奇数，因此，元素10在区间(4,5)上，即区间[9,16]

假设查找18：

二分查找不命中，返回index=-7，(-7+1)*(-1)=6，说明元素18可插入在数组下标为6的位置处。由于6是个偶数，因此，元素18不在任何一个区间。

。。。。

总之，结合数组长度永远是偶数(区间对)，再结合二分查找返回的“数组下标”是否为奇偶，是否命中，是可以实现：给定一个数，快速地判断这个数是否落在某个区间？若落在了某个区间，则具体是哪个区间上的。

另外一种形式的范围查询：

在elasticsearch中，也有RangeQuery，它是基于kd树实现的，能够快速地针对大量的数据进行范围查找。

------------------------------------------------------

五，代码实现

假设所有的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 intparse() {2 JSONReader jsonReader = null;3 int index = 0;4 try{5 jsonReader = new JSONReader(new FileReader(newFile(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(newAddress(ipInfo.getCountry(), ipInfo.getProvince(), ipInfo.getCity()));16 recordNum++;17 }18 jsonReader.endArray();//---> ]

19 jsonReader.close();20 returnrecordNum;21 }

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

1 private static longtoSmallLongFromIpAddress(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, longsearchNumber) {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, longsearchNumber) {intmid;

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]

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

returnhigh;

}

Address类的代码如下：

public classAddress {privateString country;privateString province;privateString city;publicAddress() {//TODO Auto-generated constructor stub

}publicAddress(String country, String province, String city) {this.country =country;this.province =province;this.city =city;

}publicString getCountry() {returncountry;

}public voidsetCountry(String country) {this.country =country;

}publicString getProvince() {returnprovince;

}public voidsetProvince(String province) {this.province =province;

}publicString getCity() {returncity;

}public voidsetCity(String city) {this.city =city;

}

@OverridepublicString toString() {return "country: " + country + ", province: " + province + ", city: " +city;

}

}

View Code

与Address类一样，IpInfo类也是个JAVA Bean，只是比Address类多了两个属性而已，这两个属性是：begin_int_ip 和 end_int_ip

整个完整代码实现如下：(自己测试了下，由于使用fastjson 将数据都加载到内存了，因此查找IP还是非常快的 ^~^)

importjava.io.File;importjava.io.FileNotFoundException;importjava.io.FileReader;importjava.util.ArrayList;importjava.util.List;importcom.alibaba.fastjson.JSONReader;public classFindIp {private static final String FILE_PATH = "F:\\ipJson.conf";private static final int RECORD_NUM = 1065589;//ipJson.conf中一共约有100万条IP地址段数据

private long[] ipSegments;private static List

ipRegions;publicFindIp() {

ipSegments= new long[RECORD_NUM * 2];//每个区间 有起始位置和终点位置 [startPos, endPos]

ipRegions = new ArrayList

(RECORD_NUM);

}public static voidmain(String[] args) {

FindIp fip= newFindIp();

fip.parse();//将json格式的数据解析出来,然后放到 查找数组中.

String[] ips = { "122.246.89.69", "183.228.145.144", "36.99.63.196", "124.114.242.174", "183.10.202.232"};long startTime =System.currentTimeMillis();for(String ip : ips) {

Address address=fip.find(ip);

System.out.println("ip: " + ip + ", address:" +address);

}long endTime =System.currentTimeMillis();

System.out.println("find five ip address use time:" + (endTime - startTime) + "ms");

}private intparse() {

JSONReader jsonReader= null;int index = 0;try{

jsonReader= new JSONReader(new FileReader(newFile(FILE_PATH)));

}catch(FileNotFoundException e) {

}int recordNum = 0;

jsonReader.startArray();//---> [

while(jsonReader.hasNext()) {

IpInfo ipInfo= jsonReader.readObject(IpInfo.class);//根据 java bean 来解析

ipSegments[index++] =ipInfo.getBegin_int_ip();

ipSegments[index++] =ipInfo.getEnd_int_ip();

ipRegions.add(newAddress(ipInfo.getCountry(), ipInfo.getProvince(), ipInfo.getCity()));

recordNum++;

}

jsonReader.endArray();//---> ]

jsonReader.close();returnrecordNum;

}publicAddress find(String ip) {long startTime =System.currentTimeMillis();long ipConvert = toSmallLongFromIpAddress(ip);//System.out.println("ip:" + ip + ", convertInt:" +ipConvert);int index =binarySearch(ipSegments, ipConvert);if (index == -1)return new Address();//未找到,返回一个没有任何信息的地址(avoid null pointer exception)

Address addressResult= ipRegions.get(index / 2);long endTime =System.currentTimeMillis();

System.out.println("find: " + ip + " use time: " + (endTime -startTime));returnaddressResult;

}private int binarySearch(long[] arr, longsearchNumber) {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, longsearchNumber) {intmid;

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]

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

returnhigh;

}private static longtoSmallLongFromIpAddress(String strIp) {long[] ip = new long[4];

String[] ipSegments= strIp.split("\\.");for (int i = 0; i < 4; i++) {

ip[i]=Long.parseLong(ipSegments[i]);

}return (ip[0] << 24) + (ip[1] << 16) + (ip[2] << 8) + ip[3];

}

}

View Code

时间复杂度分析：假设共有N条IP区间数据，根据IP找该IP对应的区间，使用的是二分查找，时间复杂度为O(logN)。找到之后，根据区间的在long[]数组中的 索引 来定位该区间对应的地区，时间复杂度为O(1)，故总的时间复杂度为O(logN)

空间复杂度分析：N条 IP区间需要 2*N个数组元素保存(因为每个区间上起始位置和结束位置)，IP区间对应的地址信息使用长度为N的 ArrayList保存，空间复杂度为O(2*N)+O(N)=O(N)

六， 参考资料：