二分查找
一、什么是二分查找?
二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0 。
比如，我们要在下图所示的有序数组中，查找值为19的数据。
target = 19；
- low=0，high=9，mid=(low+high)/2=4；mid所在位置值大于target值，high=mid-1
- low=0, high=mid-1=3, mid=(low+high)/2=1; mid所在位置值小于target，low=mid+1
- low=mid+1=2, high=3, mid=2; mid所在位置值等于target，查找结束。
二、过程分析
-
假设数据大小是n，每次查找后数据都会缩小为原来的一半，最坏的情况下，直到查找区间被缩小为空，才停止。所以，每次查找的数据大小变化是:
当n/(2^k)=1时。k的值就是总共比较的总次数，而每次缩小操作只涉及两个数据的大小比较，所以经过k次区间缩小操作，时间复杂度位O(k)。
通过n/(2^k)=1，可求得k=log2n，所以时间复杂度是O(logn)。
-
认识O(logn)
这是一种极其高效的时间复杂度，因为logn是一个非常“恐怖“的数量级，即便n非常大，对应的logn也很小。比如n等于2的32次方，也就是42亿，而logn才32。
代码示例
普通二分查找
/*
二分查找：
1，应用环境：
a，依赖顺序表结构
b，有序
2，普通二分查找，循环实现
*/
func BSearch(arr []int, target int) int {
low, high := 0, len(arr)-1
for low <= high { //注意点1:循环退出条件是low <= high
mid := low + ((high - low) >> 1) //注意点2: mid声明位置以及取值，避免溢出，位运算高效
if arr[mid] < target {
low = mid + 1 //注意点3:low和high更新是加减1的操作
} else if arr[mid] > target {
high = mid - 1
} else {
return mid
}
}
return -1
}
/*
普通二分查找：递归实现
*/
func BSearch2(arr []int, target int) int {
return recurBSearch(arr, 0, len(arr)-1, target)
}
func recurBSearch(arr []int, low, high, targt int) int {
if low > high {
return -1
}
mid := low + ((high - low) >> 1)
if arr[mid] == targt {
return mid
} else if arr[mid] > targt {
return recurBSearch(arr, low, mid-1, targt)
} else {
return recurBSearch(arr, mid+1, high, targt)
}
}
二分查找变种
/*
二分查找变种1：查找第一个值等于目标值的元素
*/
func FindFirstTarget(arr []int, target int) int {
low, high := 0, len(arr)-1
for low <= high {
mid := low + ((high - low) >> 1)
if arr[mid] < target {
low = mid + 1
} else if arr[mid] > target {
high = mid - 1
} else { //特殊之处，当mid已经是0号位置，或者mid-1位置值不是target时，
//表明mid就是第一个等于target值的位置
if mid == 0 || arr[mid-1] != target {
return mid
}
high = mid - 1
}
}
return -1
}
/*
二分查找变种2：查找最后一个值等于目标值的元素
*/
func FindLastTarget(arr []int, target int) int {
arr_length := len(arr)
low, high := 0, arr_length-1
for low <= high {
mid := low + ((high - low) >> 1)
if arr[mid] < target {
low = mid + 1
} else if arr[mid] < target {
high = mid - 1
} else { //特殊之处
if mid == arr_length-1 || arr[mid+1] != target {
return mid
}
low = mid + 1
}
}
return -1
}
/*
二分查找变种3：查找第一个大于等于目标值的元素
*/
func FindFirstGETarget(arr []int, target int) int {
low, high := 0, len(arr)-1
for low <= high {
mid := low + ((high - low) >> 1)
if arr[mid] < target {
low = mid + 1
} else { //特殊之处
if mid == 0 || arr[mid-1] < target {
return mid
}
high = mid - 1
}
}
return -1
}
/*
二分查找变种4：查找最后一个小于等于目标值的元素
*/
func FindLastLETarget(arr []int, target int) int {
arr_length := len(arr)
low, high := 0, arr_length-1
for low <= high {
mid := low + ((high - low) >> 1)
if arr[mid] <= target { //特殊之处
if mid == arr_length-1 || arr[mid+1] > target {
return mid
}
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
示例
/*
二分查找应用：计算数字x的平方根，精度要求为y
*/
func ComputeSqureRoot(x, y float64) float64 {
if x < 0 {
return -1
}
if x == 1 || x == 0 {
return x
}
var low, high float64
high = x
if x < 1 {
low = 0
} else {
low = 1
}
for low <= high {
mid := low + (high-low)/2
temp := mid * mid
if temp+y >= x && temp-y <= x {
return mid
} else if temp < x {
low = mid
} else {
high = mid
}
}
return -1
}
应用前提
- 存储结构依赖顺序表结构，即数组
- 针对的是有序数据
应用建议
- 二分查找适用于一次排序多次查找的场景中。
- 二分查找适用于单次比较非常耗时，需尽量减少比较次数的场景。
- 二分查找不适用于数据量太大的场景，因为二分查找需要连续内存。
应用实例
- 快速定位ip地址的归属地?
a：先把ip地址转换为32位整数
b：对这12万个ip地址升序排序
c：在有序ip数组中，查找最后一个小于等于目标ip的数值
- leetcode编程题：搜索旋转排序数组
文章最后发布于: 2019-05-07 15:26:35
相关阅读
二分图匹配，自然要先从定义入手，那么二分图是什么呢？ 二分图： 二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如
二分法定义：在一个单调有序的集合中查找元素，每次将集合分为左右两部分，判断解在哪个部分中并调整集合上下界，重复直
将不连续编号替换成连续编号：Word查找替换高级玩法(09)
当我们在Word对某些段落或句子使用编号的时候就要注意了，之前按照顺序排好的编号，却在我们书写完成甚至已经调好格式的时候恍然发现
简介 二分法插入排序没有排序，只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始，向后移动一位，再移动倒数第2位，直
常见的搜索方法：顺序查找、二分法查找、二叉树查找、哈希查找。 二分法查找 二分查找又称折半查找，优点是比较次数少，查找速度快，平均