引言

有一个比较简单的游戏，就是猜数字。 从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次，1次比较即可，所以算法的时间复杂度为o[k]，n//k

二分查找算法的局限性

二分搜索算法虽然高效，但简单的二分搜索应用范围并不广泛。 主要原因：

要求是有序排列的结构。 否则，对于链表，随机获取中间元素的时间复杂度是o(n )，而不是常数时间。 数组不能太小。 如果只进行数据检索，则数组太小或太小都没有区别。 如果比较两个数据需要时间，则最好在两分钟内进行搜索。 数组不能太大。 如果太大，数组占用的空间会很大。 此外，请求区域必须是连续的。 这对内存的要求很高。

二分查找算法代码实现

公共类测试搜索{

静态搜索(inta [ ]，int size，int searchValue )。

int low=0；

int high=size - 1；

使用high-low是为了防止数组过大，或者两个数相加而溢出，使用移位是为了提高性能

int mid=(高低) 1低；

while(low=high ) {

if (a [ mid ]搜索值) {

high=mid - 1；

}elseif(a[mid]searchvalue ) )

low=mid 1；

}elseif(a[mid]==searchvalue ) {

返回mid；

}

mid=(高低)1)低；

}

返回- 1；

}

静态搜索2 (inta [ ]，int size，int searchValue )。

returnbsearchinter(a，0，size - 1，searchValue )；

}

staticintbsearchinter(inta[]，int low，int high，int searchValue ) {

if (低高度) {

返回- 1；

}

int mid=(高低)1)低；

if(a[mid]==searchvalue ) {

返回mid；

}elseif(a[mid]searchvalue ) )

returnbsearchinter(a，low，mid - 1，searchValue )；

} else {

returnbsearchinter(a，mid 1，high，searchValue )；

}

}

publicstaticvoidmain (字符串[ ] args ) {

inta [ ]={ 1，4，5，77，333，980，1245 }；

int seachValue=1245；

intindex=bsearch(a，7，seachValue )；

If (索引！=-1 ()

system.out.println (findindex : ) index )；

} else {

system.out.println (' not find data : ' seach value )；

}

索引2=bsearch2(a，7，seachValue )；

If (索引！=-1 ()

system.out.println (findindex 2: ) index )；

} else {

system.out.println (' not find data : ' seach value )；

}

}

}

二分查找算法的用途

简单的二分搜索由于受上述条件的限制，用途并不广泛。 在很多情况下，我们喜欢使用哈希表，但是如果搜索特殊情况下的元素(如搜索大于或等于最后一个值的数据)，查找第一个值小于或等于预定值的元素，则通过二分查找可以有效地解决问题。 例如，在进行IP范围段的匹配时，为了判断IP是否属于IP段的集合并确定其所属的地域，首先将IP转换为int，IP的段将第一个IP和最后一个IP都转换为int，然后获得的inip 查询后，将此查询的ip与查询的最后一个ip段的末尾进行比较。 如果小于，则此ip属于指定的ip段。 下图：

将一系列IP段转换为段。 图中的段a-b是IP段的范围。 其中，a是该IP段的起始地址，b是该IP段的结束地址。 查询时，我们查询最后给出的IP以下几点。 设这一点为c，则判断给定的IP是否在d以下。 如果IP表明它属于CD所属的IP段； 如果大于d且小于e，则在此IP段中找不到此IP。

本篇为《数据结构和算法之美》课程整理。