如何快速定位IP对应的省份
二分查找的四种变形：查找第一个值等于给定值得元素，查找最后一个值等于给定值得元素，查找第一个大于等于给定值得元素，查找最后一个小于等于给定值得元素。
同时，今天的这四种情况，给定数据集合同样是有序的，但是却有重复元素。
变体一：查找第一个值等于给定值得元素
先看代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public static int searchOne(int[] list,int num){
int low = 0;
int high = list.length - 1;
while(low <= high){
int mid = (high + low)/2;
if(list[mid] > num){
high = mid - 1;
}else if(list[mid] < num){
low = mid + 1;
}else{
if(list[mid] == num && list[mid - 1] < num){
return mid;
}else{
high = mid - 1;
}
}
}
return -1;
}
上述代码中，对于 list[mid] 大于或者小于给定值的判断逻辑很好理解，重点解释下 list[mid] 等于给定值的时候如何做出判断。
当 list[mid] 等于给定值得时候，因为数组是按照从小到大顺序排列，所以我们要根据 mid 前一位的值做出后续的逻辑判断。如果 list[mid - 1] 小于给定值，则证明 mid 位置上是第一个给定值的元素，否则就需要令 high = mid - 1，继续二分查找。
变体二：查找最后一个值等于给定值得元素
先看代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//二分法查找变体二，查找最后一个值等于给定值得元素
public static int searchTwo(int[] list,int num){
int low = 0;
int high = list.length - 1;
while(low <= high){
int mid = (high + low)/2;
if(list[mid] > num){
high = mid - 1;
}else if(list[mid] < num){
low = mid + 1;
}else{
if(list[mid] == num && list[mid + 1] > num){
return mid;
}else{
low = mid + 1;
}
}
}
return -1;
}
当 list[mid] 等于给定值得时候，因为数组是按照从小到大顺序排列，所以我们要根据 mid 前一位的值做出后续的逻辑判断。如果 list[mid + 1] 大于给定值，则证明 mid 位置上是最后一个给定值的元素，否则就需要令 low = mid + 1，继续二分查找。
变体三：查找第一个值大于给定值得元素
先看代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//二分法查找变体三，查找第一个值大于给定值得元素
public static int searchThree(int[] list,int num){
int low = 0;
int high = list.length - 1;
while(low <= high){
int mid = (high + low)/2;
if(list[mid] > num){
high = mid - 1;
}else if(list[mid] < num){
low = mid + 1;
}else{
if(list[mid] == num && list[mid + 1] > num){
return mid + 1;
}else{
low = mid + 1;
}
}
}
return -1;
}
当 list[mid] 等于给定值得时候，因为数组是按照从小到大顺序排列，所以我们要根据 mid 前一位的值做出后续的逻辑判断。如果 list[mid + 1] 大于给定值，则证明 mid + 1 位置上第一个值大于给定值得元素，否则就需要令 low = mid + 1，继续二分查找。
变体四：查找第一个值小于给定值得元素
先看代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//二分法查找变体四，查找第一个值小于给定值得元素
public static int searchFour(int[] list,int num){
int low = 0;
int high = list.length - 1;
while(low <= high){
int mid = (high + low)/2;
if(list[mid] > num){
high = mid - 1;
}else if(list[mid] < num){
low = mid + 1;
}else{
if(list[mid] == num && list[mid - 1] < num){
return mid - 1;
}else{
high = mid - 1;
}
}
}
return -1;
}
当 list[mid] 等于给定值得时候，因为数组是按照从小到大顺序排列，所以我们要根据 mid 前一位的值做出后续的逻辑判断。如果 list[mid - 1] 小于给定值，则证明 mid - 1 位置上第一个值大于给定值得元素，否则就需要令 high= mid - 1，继续二分查找。
如何快速定位IP对应的省份
因为 IP 地址可以转化为 32 位整数，所以先对IP地址数据排序。然后用二分查找找到第一个 IP 起始地址小于给定地址的数据，然后在判断给定地址是否在该数据 IP 区间。
总结
本文创作灵感来源于 极客时间 王争老师的《数据结构与算法之美》课程，通过课后反思以及借鉴各位学友的发言总结，现整理出自己的知识架构，以便日后温故知新，查漏补缺。
初入算法学习，必是步履蹒跚，一路磕磕绊绊跌跌撞撞。看不懂别慌，也别忙着总结，先读五遍文章先，无他，唯手熟尔~
与诸君共勉