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

smallBird · 2020-07-12 00:56:23 · 2177 次点击 · 大约8小时之前 开始浏览    置顶
这是一个创建于 2020-07-12 00:56:23 的主题,其中的信息可能已经有所发展或是发生改变。

小白上车 = 二分查找--最最简单的算法

一、什么是二分查找

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

二、 前提

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, 说明我们还可以继续进行查找 。

那么基于这个逻辑我们在循环里面进行更新。 如下代码

四、代码

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


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

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

2177 次点击  
加入收藏 微博
2 回复  |  直到 2020-11-25 10:46:50
sdszilong
sdszilong · #1 · 4年之前

楼主的这个模板不是LEETCODE里面刷二分法最好的模板,会有很多边界和corner case考虑不到的地方。 九章培训班的那个模板是最好的!

GotoLove-LoonGL
GotoLove-LoonGL · #2 · 4年之前
sdszilongsdszilong #1 回复

楼主的这个模板不是LEETCODE里面刷二分法最好的模板,会有很多边界和corner case考虑不到的地方。 九章培训班的那个模板是最好的!

九章培训班???在哪儿看模板

添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传