# 小白上车 = 二分查找--最最简单的算法
#### 一、什么是二分查找
生活中。我们经常用到这个类似的方法,查字典。我们在查一个单词,尤其是一个首字母不在最前不在最后,不在中间的单词,大致的逻辑是这样的: 字典真的不薄,因此我们估算不出来那块就我们要的范围。 那么先翻他一半,他不香吗。 以此类推,如果字符在前半部分,就去前半部分在一半。 基本重复这个操作就可以迅速查到自己想要的单词。 二分查找就是这样。下面我们继续看
#### 二、 前提
1 在有序的切片或这数组中进行查找。这里的有序不区分升序,降序
2 这里我们仅仅对元素所在的下标进行搜索查找。
3 有一个目标值。我们约定如果不在数组里面就返回一个-1
#### 三、逻辑梳理以及算法
二分查找是我们常用的一种逻辑思路,也就是算法。比其更差的算法当时基础的全遍历。
我们到这起码知道的是 有序。 范围减半。因此二分法最核心的部分就是范围减半在范围减半。
通常来说,比如我们先拿到中间的值和我们目标的值,进行比较,如果大的话就取上半区域。如果小的话就取下半区域。
如果等于 ,说明找到了。
初始状态,假定函数是这样的binarySearch(目标值。数组)。同时数组的第一个位置为low, 最后一个位置为high. 那么中间值显而易见是 low + high = 中间值
第一: if 目标值 > 数组【中间值】, 这表示目标值在后面的部分,那我们就需要在 mid +1 到high 这个范围内进行在次二分查找,这个时候,mid+1 其实就是第二次二分查找的low .
第二: if 目标值 < 数组【中间值】(数组的中间值已经更新), 这表示目标值在前面的部分,那我们就需要在 low 到 mid+1这个范围内进行在次二分查找,这个时候,mid-1 其实就是第二次二分查找的high.
第三:if 目标值 = 数组【中间值】(数组的中间值已经更新)那么,直接输出下标。
我们从上述的逻辑中可以看出, 我们一直在更新low 和high,让low 变大。让high 变小。这么当这两个重合的时候,就是最后一次要进行比较的时候。 这个时候如果仍然不能满足目标值等于数组中间值。那么程序的驱动是low 和high 有一个必然会变的更小。 及这个时候low > high, 那么只要low <= high, 说明我们还可以继续进行查找 。
那么基于这个逻辑我们在循环里面进行更新。 如下代码
#### 四、代码
```go
func BinarySearch(k int,a []int)int{
low := 0
high := len(a)-1
for low <= high {
mid := (low + high) / 2
if k > a[mid] {
low = mid + 1
}else if k < a[mid] {
high = mid - 1
}else {
return mid
}
}
return -1
}
```
#### 五、时间复杂度
假设有1000 个数组。 假设我们要一直查到low == high ,意味这什么呢:
第一次 : 1000/2
第一次 : 500/2
第一次 : 250/2
基本要10次
。。。。。
其实显而易见了。 2X= N 那么 K= log2N
二分查找的算法复杂度为O(log2N)
再来和全遍历O(N)比较下.当数量级大到一定程度的时候,其效果不言而喻。
![image.png](https://static.studygolang.com/200712/984253be42e25bea2930d34f2ada2f80.png)
有疑问加站长微信联系(非本文作者)