数一数分一分比一比怎么教（从猜数字到二分法）
数一数分一分比一比怎么教（从猜数字到二分法）我们将一系列IP段都转成线段，图中线段AB就是一个IP段的范围，其中A是这个IP段的起始地址，B是这个IP段的终止地址。 查询的时候，我们就是要查询最后一个小于等于给定IP的点，假如这个点为C，那么判断给定IP是不是小于等于D，如果是说明IP属于CD所归属的IP段；如果大于D，且小于E，说明此IP在这一堆IP段中找不到。 public class TestBinSearch { static int bsearch(int a[] int size int searchValue) { int low = 0; int high = size - 1; //用high-low 是为了防止数组过大，两数相加溢出，用移位是为了提升性能 int mid = (high - low) >> 1 low;
引言有个比较简单的游戏，叫猜数字， 从0-1000之间随便想一个数字，让对方猜，给出数字大了或小了的提示，看谁用最短的次数来猜出数字。 猜猜，0-1000之间数字，最少需要用多少次，最多只需要用10次就可以猜中结果，即使数字范围扩大到42亿，也只需要32次就可以猜中结果，是不是很快?
如果让我们自己想，如何快速猜中要猜测的数字那，数字只所以难猜中是因为范围比较大。要想快速地猜中数字，需要缩小数字的范围，比如这0-1000这个数字，第一次猜测为500，对方如果反馈数字大了，则说明要猜测的数字在0-499之间，如果反馈真实数字比500大，那么说明要猜测的数字就在501-999之间，这种想法就是今天要介绍的二分法 说起来很简单吧。
总结下，二分查找算法就是在对有序集合的数据查找过程中，每次都取中间值，这样把每次的查询区间都缩小了一半，直到找到元素或者查找的集合缩小为0。
二分查找的算法执行时间分析以下为算法的时间复杂度分析，查找区间依次为：
n，n/2 n/22 n/23 n/24 ...n/2k...
查找结束的条件是查找到元素或者区间为1，当n/2k=1 的时候说明要查找的区间已经变为了1，那么总共需要查找的缩小的次数为k次，而每次只需要比较一次，所以算法的时间复杂度为O(k) 根据n/2k=1得到k = log2n，根据时间复杂度的简写算法可以写成O(logn) 这是非常优秀算法。
二分查找算法的局限性二分查找算法虽然高效，但是简单的二分查找的应用范围并不广泛，主要原因：
- 要求是有序的数组的结构，不然如果是链表，随机取中间元素的时间复杂度就是O(n)而不是常量时间了。
- 数组不能太小，如果仅仅做数据查找，数组不能太小，太小差异不大，如果两个数据的比较比较耗时，用二分查找还是适合的。
- 数组不能太大，太大的话，数组的占空间比较大，而且要求空间必须是连续的，这个对内存要求高。
public class TestBinSearch {
static int bsearch(int a[] int size int searchValue) {
int low = 0;
int high = size - 1;
//用high-low 是为了防止数组过大，两数相加溢出，用移位是为了提升性能
int mid = (high - low) >> 1 low;
while (low <= high) {
if (a[mid] > searchValue) {
high = mid - 1;
} else if (a[mid] < searchValue) {
low = mid 1;
} else if (a[mid] == searchValue) {
return mid;
}
mid = ((high - low) >> 1) low;
}
return -1;
}
static int bsearch2(int a[] int size int searchValue) {
return bsearchInter(a 0 size - 1 searchValue);
}
static int bsearchInter(int a[] int low int high int searchValue) {
if (low > high) {
return -1;
}
int mid = ((high - low) >> 1) low;
if (a[mid] == searchValue) {
return mid;
} else if (a[mid] > searchValue) {
return bsearchInter(a low mid - 1 searchValue);
} else {
return bsearchInter(a mid 1 high searchValue);
}
}
public static void main(String[] args) {
int a[] = {1 4 5 77 333 980 1245};
int seachValue = 1245;
int index = bsearch(a 7 seachValue);
if (index != -1) {
System.out.println("Find index:" index);
} else {
System.out.println("Not Find data:" seachValue);
}
int index2 = bsearch2(a 7 seachValue);
if (index != -1) {
System.out.println("Find index2:" index);
} else {
System.out.println("Not Find data:" seachValue);
}
}
}
二分查找算法的用途
简单的二分查找，受到以上条件限制，所以用途并不广泛，很多时候我们更喜欢用散列表，但是如果查找一些特殊情况的元素，比如查找最后一个大于等于给定值的数据；查找第一个值小于等于给定值的元素，就可以用二分查找高效解决，比如我们在进行IP范围段匹配的时候，如何判断给定的IP是否归属一堆IP段从而判断归属的地区，有个不错的办法，先将IP转成int，IP的段可以将起始IP和尾端IP都转成int，然后将所得的int，排序，我们就得到了一个有序的int数组，然后将要查询的ip也转成int，然后查询ip数组中最后一个值小于等于给定的ip的数据，查询到了之后再用这个要查询的IP和查询到的最后一个ip段尾比较，如果比它小，那么这个ip就属于给定的ip段。 如下图：
我们将一系列IP段都转成线段，图中线段AB就是一个IP段的范围，其中A是这个IP段的起始地址，B是这个IP段的终止地址。 查询的时候，我们就是要查询最后一个小于等于给定IP的点，假如这个点为C，那么判断给定IP是不是小于等于D，如果是说明IP属于CD所归属的IP段；如果大于D，且小于E，说明此IP在这一堆IP段中找不到。
本篇为《数据结构和算法之美》课程整理。
