搜索是我们生活的一部分，因为我们不可能总是有答案。还有各种算法可以帮助程序更有效地运行并更有效地处理数据。

我们将在本教程中介绍的内容

• 什么是搜索算法？
• 什么是二进制搜索算法？
• 二进制搜索的工作原理 – 分而治之
• 二进制搜索算法中涉及的进程
• 二进制搜索算法中使用的方法
• 二进制搜索的真实示例

什么是搜索算法？

搜索算法用于从任何数据结构中检索项目。它将作为输入的数据与存储在其数据库中的信息进行比较，并得出结果。例如，在包含 1，000 个号码的联系人列表中查找您最好的朋友的号码。

有不同类型的搜索算法。其中一些是：

线性搜索算法

线性搜索算法是所有搜索算法中最简单的。顾名思义，它们按顺序运行。

线性搜索逐个检查列表中的元素以查找特定的键值。此键值位于列表中的其他项中，算法通过检查返回位置。

迪克斯特拉算法

Dijkstra的最短路径算法用于更高级的搜索。Dijkstra的算法映射出两个节点之间的最短距离。这些节点通常是路由网络。

当您尝试在地图上查找路线时，这种类型的搜索非常有用。它根据找到尽可能短的路径为您提供了选择。

二进制搜索算法

二进制搜索算法也称为半间隔搜索。它们返回目标值在排序列表中的位置。

这些算法使用“分而治之”技术来查找值的位置。

二进制搜索算法和线性搜索算法是简单搜索算法的示例。

在二进制搜索中，在与要搜索的键值进行比较之前，会找到列表中的中间元素。但在线性搜索中，元素是通过循环并与键值进行比较来逐个获取列表中的。

在二进制搜索期间，列表被分成两部分以获取中间元素：左侧，中间元素和右侧。

左侧包含小于中间元素的值，右侧包含大于中间元素的值。此方法使用排序列表来工作。

排序列表的项目按特定顺序排列。为了使二进制搜索具有高效性，列表中的值必须按正确的顺序排列以满足搜索过程。如果列表的值混淆，则必须在执行搜索之前按排序算法对其进行排序。

排序算法

排序算法接受未排序的列表作为输入，并返回一个列表，其中的元素按特定顺序排列（主要是升序）。

有不同类型的排序算法，如插入排序、快速排序、气泡排序和合并排序。

二进制搜索的工作原理 – 分而治之

二进制搜索算法使用一种称为“分而治之”的技术来处理其任务。合并排序算法采用相同的技术对列表中的项目进行排序。

在二进制搜索算法中，“分而治之”方法的工作方式如下：

• 该算法将列表拆分为两部分：左侧和右侧，由中间元素分隔
• 它创建一个变量来存储要搜索的项目的值
• 它挑选出中间的元素，并将其与要搜索的项目进行比较
• 如果比较的项目相等，则流程结束
• 如果不是，则中间元素大于或小于您要搜索的项目。如果中间元素较大，则算法将拆分列表并搜索左侧的元素。如果中间元素较小，它将拆分列表并在列表右侧搜索元素。

您可以在二进制搜索过程中使用递归或迭代来实现此方法。

二进制搜索算法的工作原理 – 循序渐进

首先，在执行搜索之前，您需要对列表进行排序。

然后，创建一个变量来存储要搜索的值。

接下来，将列表分为两部分。我们汇总第一个和最后一个索引，以查找列表中中间元素的索引。

当中间元素索引的计算值为浮点数（如3.45）时，我们将整个部分作为索引。

然后，我们比较要搜索的值和中间元素。

二进制搜索用例

条件 1

如果中间元素等于要搜索的值，则将返回该值的位置并终止进程。

if middle element == to_search 
    return position of middle element 
*code ends* 

以上图为例：

中间元素 = 23，目标值/to_search = 23。比较这两个值，我们看到它们在两边都是相等的。23 出现在列表中的索引 2 处。这是代码的输出，过程结束。

条件 2

如果中间元素不等于“to_search”，那么我们检查以下场景：

场景 1 ：如果中间元素大于要搜索的值：

if middle element > to_search

• 搜索将移动到左侧，因为值小于中间元素
• 中间元素的位置向左移动 1
• new_position = 索引（中间元素） - 1
• 新的搜索开始，搜索在该新位置结束，它采用之前的所有值。

以上图为例：

middle element = 23
to_search = 4
if 23 > 4 

• 我们移动到左侧，因为所有小于23的数字都存储在那里。索引 （23） = 2
• new_position = 指数（23） - 1 = 2-1 = 1
• 搜索将在索引 1 处结束，并在索引 1 之前获取所有其他值

将新的中间元素（4）与目标值（4）进行比较，我们看到它们是相等的。因此，搜索终止，输出是列表中“4”占据的位置（即索引 0）。

场景 2 ：如果中间元素小于要搜索的值：

if middle element < to_search

• 搜索将移动到右侧，因为值大于中间元素
• 中间元素的位置向右移动 1
• new_position = 索引（中间元素） + 1
• 新搜索从新位置开始，到列表中的最后一个索引结束
• 所有值都取自新位置到列表末尾

以第一张图片为例：

middle element = 23 
to_search = 32 
if 23 > 32 

• 我们移动到右侧，因为所有大于23的数字都存储在那里。索引（23） = 2 ，
• new_position = 指数（23） + 1 = 2+1 = 3
• 搜索将从索引 3 开始，并在索引 3 之后获取所有其他值

将中间元素（32）与目标值（32）进行比较，我们看到它们是相等的。因此，搜索终止，输出是列表中“4”占据的位置（索引4）。

二进制搜索算法中使用的方法

有两种方法可以在搜索中实现“分而治之”技术。它们是迭代和递归。

什么是迭代？

为了从元组、列表或字典中获取元素，请使用循环循环遍历这些项。

迭代是执行过程中重复的语句序列，它具有可计数数量的值。例如，在循环访问随机列表时，我们循环访问包含列表的实际变量以获取值。

带迭代的二进制搜索的代码实现

代码如下：

def binary_search(list_num , to_search):
    first_index = 0
    size = len(list_num)
    last_index = size - 1
    mid_index = (first_index + last_index) // 2
    # print(mid_index)
    mid_element = list_num[mid_index]
    # print(mid_element)

    is_found = True
    while is_found:
        if first_index == last_index:
            if mid_element != to_search:
                is_found = False
                return " Does not appear in the list"

        elif mid_element == to_search:
            return f"{mid_element} occurs in position {mid_index}"

        elif mid_element > to_search:
            new_position = mid_index - 1
            last_index = new_position
            mid_index = (first_index + last_index) // 2
            mid_element = list_num[mid_index]
            if mid_element == to_search:
                return f"{mid_element} occurs in position {mid_index}"

        elif mid_element < to_search:
            new_position = mid_index + 1
            first_index = new_position
            last_index = size - 1
            mid_index = (first_index + last_index) // 2
            mid_element = list_num[mid_index]
            if mid_element == to_search:
                return f"{mid_element} occurs in position {mid_index}"



list_container = [16 , 18 , 20 , 50 , 60 , 81 , 84 , 89]
print(binary_search(list_container , 81))
print(binary_search(list_container , 10))

现在让我们看看这里发生了什么：

• 首先，我们传入一个列表和一个要搜索的值（to_search）作为函数的输入。
• 在函数中，我们创建第一个索引的变量名称，并将其分配给“0”。列表中的第一个索引始终为“0”。
• 然后，我们创建四个变量名称：“size”存储列表的长度，“last_index”存储最后一个元素的索引，“mid_index”存储查找中间元素索引的操作，“mid_element”存储使用中间索引作为位置从列表中获取的中间元素。
• 之后，我们引入一个 while 循环，使条件重复运行。在 while 循环上方，我们创建一个变量名称“is_found”并将其设置为“True”。此条件检查是否找到“要搜索的项目”。
• 在 while 循环中，我们检查所有条件。第一个条件是检查中间元素和变量“to_search”是否相等。如果它们相等，则将返回项目的位置。
• 然后，我们检查第二个条件（如果中间元素！=要搜索的项目），这将我们引向两种情况：- 如果中间元素大于要搜索的项目，则新位置将向左移动一次。搜索将从第一个索引开始，并在新位置结束，即新的最后一个索引。– 如果中间元素小于要搜索的项目，则新位置将向右移动一次。搜索将从作为新第一个索引的新位置开始，到最后一个索引结束。

在这些方案结束时，我们检查新的中间元素是否与要搜索的项目相同。如果相同，则将返回项目的位置。否则，将检查条件，直到值相等。

对于错误处理，假设我们要搜索列表中未显示的值。如果我们在这两个条件下结束，循环将继续运行，并可能最终使系统崩溃。

为了捕获错误，我们设置了一个条件来检查第一个索引是否等于最后一个索引。然后，我们检查中间元素是否等于要搜索的项目。如果它不相等，“被发现”将是“假的”。运行此命令时，它会显示一个空数组。在我的代码中，输出是一个语句。

最后一步是调用函数，并显示结果。

结果如下：

如果元素在列表中，则输出为位置。

如果元素不在列表中，则输出为如下语句：

什么是递归？

如果函数引用自身或以前的项来解决任务，则称其为递归函数。

递归函数是重复的，它是按顺序执行的。它从一个复杂的问题开始，并将事情分解成一种更简单的形式。

使用递归进行二进制搜索的代码实现

使用递归，它更简单一些，需要更少的代码。下面是它的外观：

def binary_search(list_num, first_index, last_index, to_search):
    if last_index >= first_index:
       
        mid_index = (first_index + last_index) // 2
        mid_element = list_num[mid_index]
       
 
        if mid_element == to_search:
            return f"{mid_element} occurs in position {mid_index}"
 
        elif mid_element > to_search:
            new_position = mid_index - 1
            # new last index is the new position
            return binary_search(list_num, first_index, new_position, to_search)
 
        elif mid_element < to_search:
            new_position = mid_index + 1
             # new first index is the new position
            return binary_search(list_num, new_position, last_index, to_search)
 
    else:
        return " Does not appear in the list"
       
list_container = [ 1, 9, 11, 21, 34, 54, 67, 90 ]
search = 34
first = 0
last= len(list_container) - 1
 
print(binary_search(list_container,first,last,search))

• 首先，函数接受四个输入：第一个索引、最后一个索引、列表和to_search（要搜索的项目）。
• 然后，我们检查最后一个索引的值是否大于或等于第一个索引的值。如果条件为真，我们将查找中间元素索引的操作分配给变量名称“mid_index”。然后使用中间索引作为位置从列表中获取中间元素。
• 我们在第一个“if”块下创建一个“if”语句，以检查中间元素和变量“to_search”是否相等。如果它们相等，则将返回项目的位置。
• 然后，我们检查第二个条件（如果中间元素！=要搜索的项目），这将引导我们进入两种情况：- 如果中间元素大于要搜索的项目，则新位置将向左移动一次。搜索将从第一个索引开始，并在新位置结束。我们返回函数并传入新位置作为最后一个索引值。– 如果中间元素小于要搜索的项目，则新位置将向右移动一次。搜索将从新位置开始，到最后一个索引结束。我们返回函数并传入新位置作为第一个索引值。
• 最后一个条件将与第一个“if”语句位于同一缩进上。如果to_search不在列表中，它将返回一个语句

最后一步是调用函数，并显示结果。

结果如下：

如果元素在列表中，则输出为位置：

如果元素不在列表中，则输出为语句：

二进制搜索的真实示例

您可能没有意识到这一点，但我们一直在执行二进制搜索。以下是您在日常生活或工作中如何使用或遇到它的一些示例：

• 在字典中搜索单词
• 在图书馆的文学部分搜索文学教科书
• 在排序列表中搜索元素
• 在根据身高排列的学生队伍中搜索身高超过5英尺3英寸的学生。

结论

在本文结束时，您应该熟悉二进制搜索算法的工作原理以及如何在代码中实现它们。

关注获取更多学习资料