学习算法-二进制搜索
大家好,如果您熟悉一些数据结构,那么现在该学习一些算法了。最基本但非常重要的主题,即二进制搜索。
我可以在不知道算法的情况下进行编码,为什么我会不愿意去学习它们呢?
当然,您可以在不技术上使用算法的情况下构建软件,这不是强制性的(我想是这样)。但是,当您解决软件问题时,您是否曾经问过自己“我能做得更好吗?”。这就是算法发挥作用的地方,最终,这种思想使您成为更好的程序员。
让我解释一下为什么它很重要。
像Facebook这样的服务拥有超过27亿用户,这意味着Facebook工程师大概必须处理大量用户的数据。有程序A和程序B处理这些数据。程序A需要1秒钟来处理每个用户的数据,而对方则需要2秒。这两个程序之间的速度差是多少?好吧,您甚至不需要计算它们,B花费的时间是A的两倍。
算法是关于如何有效地解决问题,您需要像计算机那样思考。
最广泛使用的算法是搜索和排序,今天我将讨论搜索算法。
线性搜寻
我们不能不了解线性搜索就跳入二进制搜索。您必须熟悉此算法,这是一种使用从0到数组末尾的for循环在数组中查找元素的方法。它需要n次,因为它将在这种情况下从0到5每次循环检查目标是否在索引中。线性搜索的时间复杂度为O(n)
看起来还不错,但是我们可以做得更好吗?
是的,我们可以通过使用二进制搜索使其更好。
二元搜寻
它的工作方式类似于线性搜索,但不同之处在于,它将减少一半的数组,从而减少了搜索范围,这意味着可以节省搜索时间,直到找到目标为止。
让我们在现实生活中看一下该算法。
您有一本字典来找到一个单词,您正在寻找单词“光荣”。首先,您从中间打开字典,现在在此M
部分。其次,由于该G
部分位于本书的前端,因此无需超越该M
部分。第三,因此,您在开头和M
小节之间再次随机打开,现在处于F
小节中,这意味着您将不得不在F
小节和M
小节之间查找,直到找到该G
小节。你明白了。
因此,基本上它可以缩小搜索范围,直到找到目标为止。
现在让我们更深入。我们43
将从这个数组中找到数字[14, 3, 28, 64, 43, 90]
。等等,我们不能真正使用二进制搜索,因为它的顺序不正确,无法确定搜索范围!是的…只有在对数组排序后,我们才可以进行二进制搜索。让我们先对其进行排序。
第1步。 所以,和和在这种情况下。
left = 0
right = arr.length
mid = (left + right) / 2
让我们检查一下我们当前的中点是否为目标。是28 == 43
真的吗 没有!好吧,我们现在该怎么办?因为28
小于43
,我们将left
指针移到中点的右侧。
步骤2. 由于我们向左移动了指针,所以指针将再次位于左右中间,即现在。让我们再次检查是否找到43。是真的吗?没有!然后大于或小于?大于。然后我们需要将右指针移到中点的左侧。
mid
(3 + 5) / 2 = 4 ((left+right) / 2)
64(middle) == 43(target)
64
43
64
43
步骤3. 现在,中点在索引[3]处。所以中点是。但是,如果左+右是一个多么奇怪的数字,是不是可分?例如,如果left + right是,然后将它们除以得到us ,这不是可用于索引的整数。如果您来自python背景,则将需要使用整数除法器(如),该除法器将删除小数点然后返回3。是吗?是的!让我们返回中间指针3。
left + right = 6
6 / 2 = 3
7
2
3.5
left + right // 2
43(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
- 没有金币/金币不足 怎么办?
- 本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
- 所有资源普通会员都能下载吗?
- 本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。