学习算法-二进制搜索

作者 : IT 大叔 本文共1950个字,预计阅读时间需要5分钟 发布时间: 2020-10-9

大家好,如果您熟悉一些数据结构,那么现在该学习一些算法了。最基本但非常重要的主题,即二进制搜索

我可以在不知道算法的情况下进行编码,为什么我会不愿意去学习它们呢?

当然,您可以在不技术上使用算法的情况下构建软件,这不是强制性的(我想是这样)。但是,当您解决软件问题时,您是否曾经问过自己“我能做得更好吗?”。这就是算法发挥作用的地方,最终,这种思想使您成为更好的程序员。

让我解释一下为什么它很重要。

像Facebook这样的服务拥有超过27亿用户,这意味着Facebook工程师大概必须处理大量用户的数据。有程序A程序B处理这些数据。程序A需要1秒钟来处理每个用户的数据,而对方则需要2秒。这两个程序之间的速度差是多少?好吧,您甚至不需要计算它们,B花费的时间是A的两倍
学习算法-二进制搜索插图

算法是关于如何有效地解决问题,您需要像计算机那样思考。
最广泛使用的算法是搜索和排序,今天我将讨论搜索算法

线性搜寻

我们不能不了解线性搜索就跳入二进制搜索。您必须熟悉此算法,这是一种使用从0到数组末尾的for循环在数组中查找元素的方法。它需要n次,因为它将在这种情况下从0到5每次循环检查目标是否在索引中。线性搜索的时间复杂度为O(n)

学习算法-二进制搜索插图(2)

看起来还不错,但是我们可以做得更好吗?
是的,我们可以通过使用二进制搜索使其更好。

二元搜寻

它的工作方式类似于线性搜索,但不同之处在于,它将减少一半的数组,从而减少了搜索范围,这意味着可以节省搜索时间,直到找到目标为止。

让我们在现实生活中看一下该算法。

您有一本字典来找到一个单词,您正在寻找单词“光荣”。首先,您从中间打开字典,现在在此M部分。其次,由于该G部分位于本书的前端,因此无需超越该M部分。第三,因此,您在开头和M小节之间再次随机打开,现在处于F小节中,这意味着您将不得不在F小节和M小节之间查找,直到找到该G小节。你明白了。

因此,基本上它可以缩小搜索范围,直到找到目标为止。

现在让我们更深入。我们43将从这个数组中找到数字[14, 3, 28, 64, 43, 90]。等等,我们不能真正使用二进制搜索,因为它的顺序不正确,无法确定搜索范围!是的…只有在对数组排序后,我们才可以进行二进制搜索。让我们先对其进行排序。

第1步。 所以,和和在这种情况下。
学习算法-二进制搜索插图(4)
left = 0right = arr.lengthmid = (left + right) / 2

让我们检查一下我们当前的中点是否为目标。是28 == 43真的吗 没有!好吧,我们现在该怎么办?因为28小于43,我们将left指针移到中点的右侧。

步骤2. 由于我们向左移动了指针,所以指针将再次位于左右中间,即现在。让我们再次检查是否找到43。是真的吗?没有!然后大于或小于?大于。然后我们需要将右指针移到中点左侧
学习算法-二进制搜索插图(6)
mid(3 + 5) / 2 = 4 ((left+right) / 2)64(middle) == 43(target)64436443

步骤3. 现在,中点在索引[3]处。所以中点是。但是,如果左+右是一个多么奇怪的数字,是不是可分?例如,如果left + right是,然后将它们除以得到us ,这不是可用于索引的整数。如果您来自python背景,则将需要使用整数除法器(如),该除法器将删除小数点然后返回3。是吗?是的!让我们返回中间指针3。
学习算法-二进制搜索插图(8)
left + right = 66 / 2 = 3723.5left + right // 243(middle) == 43(target)

您采取了多少步骤才能找到43?

我们花了3步,如果n是数组的长度,我们大约花了n / 2步,这比线性搜索要短得多,并且对于N的大小,它会变得更小,如果N的大小很大。因此,我们完成了n次工作的一半,可以表示为1/2 * 1/2 * 1/2 * 1/2 * 1/2 = log5(假设对数为2)。因此,时间复杂度为O(log2N)

实作

二进制搜索有两种实现方式,即迭代递归。为了简单起见,我将给出一个迭代的实现示例。在类似python的伪代码中:

def binary_search(arr, target):
  left = 0
  right = arr.length - 1
  while left <= right:
    mid = (left + right) // 2
    # When found target
    if arr[mid] == target:
      return mid
    # When target is less than midpoint value
    elif target < arr[mid]:
      right = mid - 1  # move right pointer to left of mid
    # When target is greater than midpoint value
    else:
      left = mid + 1  # move left pointer to right of mid
  return -1

希望您觉得这对您的计算思想有用,稍后我将进一步讨论算法!感谢您的阅读!

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 学习算法-二进制搜索

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论