go算法基础系列-最最基础二分法（立贴）

# 小白上车 = 二分查找--最最简单的算法 #### 一、什么是二分查找 生活中。我们经常用到这个类似的方法，查字典。我们在查一个单词，尤其是一个首字母不在最前不在最后，不在中间的单词，大致的逻辑是这样的： 字典真的不薄，因此我们估算不出来那块就我们要的范围。 那么先翻他一半，他不香吗。 以此类推，如果字符在前半部分，就去前半部分在一半。 基本重复这个操作就可以迅速查到自己想要的单词。 二分查找就是这样。下面我们继续看 #### 二、 前提 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)比较下.当数量级大到一定程度的时候，其效果不言而喻。