龙空技术网

Python中的二进制搜索算法

易小盟办公设备企业店 178

前言:

现时小伙伴们对“python读二进制”大体比较注重,大家都需要了解一些“python读二进制”的相关知识。那么小编同时在网上网罗了一些有关“python读二进制””的相关资讯,希望同学们能喜欢,朋友们快快来学习一下吧!

二进制搜索算法是计算机科学的基础。 与效率较低的方法相比,这是一种非常聪明的算法,可大大减少在大型数据集中搜索项目所需的时间。

重要的是要注意,为了使用二进制搜索,必须对数据进行排序。 有些人将排序算法和搜索算法混为一谈,将它们归为一类,但是花一点时间组织一下“算法工具包”是很值得的,并确保搜索和排序都有自己的部分。 提醒一下,请参阅以下列表,以获取每个示例的一些示例:

搜索算法线性搜索二进制搜索排序算法气泡排序插入排序合并排序快速分类二进制搜索算法如何工作?

本文介绍二进制搜索以及如何使用Python编写二进制搜索。在用代码或伪代码编写代码之前,您需要全面了解该过程,最好通过在纸上或白板上手工编写大量示例来完成此过程。通过与朋友玩猜谜游戏,您可以很好地了解算法的工作原理。

一个玩家想到一个介于1到64之间的数字,另一个玩家尝试猜测它是什么。对于每个猜测,知道该数字的玩家将告诉其他玩家他们的猜测是否正确,或者他们认为的数字是否高于该猜测。

如果您几次玩此游戏,您会很快发现某些猜数字的策略比其他策略更有效。例如,假设原始数字为13,而您猜为50。您被告知您的猜测过高。下一个猜测49不是一个好选择。为了最大程度地减少猜测数字的机会,最好的策略是在实际值的已知上限和下限之间猜测一半。因此,如果您知道数字在1到64之间,则应该猜到32。如果得知数字太高,则应该猜到16,依此类推。每次您将搜索空间减半时,都可以保证在相对较少的步骤中找到答案。这就是二进制搜索如何工作的本质。

二进制搜索的伪代码

如果您正在为考试而学习计算机科学,则可能需要为二进制搜索算法编写伪代码。以下是使用与英国OCR考试委员会的伪代码指南兼容的语法的版本。我个人认为此步骤在教学上是多余的,正如我在题为“我们需要讨论伪代码”的文章中所解释的那样,但我在此添加了该步骤,因为它可能对某些人有所帮助。

// Binary search algorithm Pseudocode (OCR)haystack = [7, 7, 22, 37, 47, 55, 57, 57, 86, 91] // MUST be sortedneedle = int(input("Enter the number you are searching for: "))length = haystack.lengthlower_bound = 0upper_bound = length - 1found = Falsewhile found == False and lower_bound <= upper_bound:    mid_point = (lower_bound + upper_bound) DIV 2    if haystack[mid_point] == needle:        print("You number has been found.")        found = True    elif haystack[mid_point] < needle:        lower_bound = mid_point + 1    else:        upper_bound = mid_point - 1        endifendwhileif found == False:    print("Your number is not in the list.")endif

该算法使用了一种重要技术,称为视频中提到的分而治之。在每个阶段,将数据集的一半丢弃,并将算法重新应用于其余的较小数据集,直到找到搜索项或满足退出条件为止。

此退出条件是该算法的关键,并且了解为什么它是什么是您了解整个算法的一个好兆头。从本质上讲,我们有一个高指针和一个低指针,我们检查这两个指针中间的项是否是我们的搜索项。如果是,那就好的,我们退出,否则,我们将高或低指针移动到“夹住”我们的价值的方式。

Python中的二进制搜索

编写并理解了伪代码后,就该用一种真正的编程语言(例如Python)编写算法了。您应该始终牢记一个特定的示例,以测试程序的行为是否符合预期。因此,定义一个列表(我经常将其称为大海捞针)和一个搜索项(针),然后看是否可以让您的程序在大海捞针中找到针。请记住:该列表必须首先排序!

现在就去,完成或陷入困境并需要帮助时,请在下面查看我的版本。

"""Basic binary search algorithm"""haystack = [7, 7, 22, 37, 47, 55, 57, 57, 86, 91]needle = int(input("Enter the number you are searching for: "))length = len(haystack)lower_bound = 0upper_bound = length - 1found = Falsewhile found == False and lower_bound <= upper_bound:    mid_point = (lower_bound + upper_bound) // 2    if haystack[mid_point] == needle:        print("You number has been found.")        found = True    elif haystack[mid_point] < needle:        lower_bound = mid_point + 1    else:        upper_bound = mid_point - 1if found == False:    print("Your number is not in the list.")

标签: #python读二进制