go算法基础系列-最最基础二分法(立贴)

smallBird · · 2121 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

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

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2121 次点击  
加入收藏 微博
2 回复  |  直到 2020-11-25 10:46:50
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传