在Python中执行二分查找

excelperfect

标签：Python，二分查找

本文将展示二分查找算法的工作原理，并提供完整的示例代码，帮助你在Python中执行自己的二分查找。

什么是二分查找算法

二分查找算法，也称为对数查找或半间隔查找，是一种在排序数组中查找项目位置/索引的查找算法。之所以被称为二分查找算法，是因为它在查找项目位置时将数组分为两部分。

需要注意的是，在使用二分查找算法查找数组中的项目之前，数组或列表必须按升序排序。

下面是一个例子。假设要在初始化已排序的nums列表中查找整数15。

nums = [4,9,15,21,25,28,35,38,40,45]

开始时，起始索引将为0，最终索引将是该数组中最后一项的索引9，中间索引将为4。二分查找算法使用下面的公式计算中间索引：

start index + (end index – start index) // 2 = 4

上面脚本中的双正斜杠指定只返回整数部分，因此尽管9/2=4.5，但中间索引将为4。

第4个索引项为25。然而，我们正在寻找小于25的项目15。因此，整数25（包括整数25）右侧的子列表将被截断。算法将开始在以下数组中查找项15：

nums = [4,9,15,21]

这说明了为什么必须对列表或数组进行排序的重要性。二分查找将再次找到一个新的中间索引，即索引1。索引1处的项为9。由于要查找的项目15大于9，因此整数9（包括9）左侧的列表将被截断，剩下的列表如下：

nums = [15,21]

在这种情况下，新的中间索引将是原始数组（[4,9,15,21,25,28,35,38,40,45]）的索引2。在当前中间索引15处再次查找该项，结果匹配，返回其索引2。

如果开始索引大于结束索引，但在每次迭代期间在中间索引处未找到该项，则意味着该项不存在于该数组中。

二分查找算法在Python中的实现

下面是在Python中实现自己的二分查找算法需要执行的步骤：

1.初始化三个变量：开始索引、结束索引和中间索引。开始索引将从0开始，结束索引将是列表或数组中最后一项的索引，例如，在前面的示例中为9，中间索引将是：开始索引+（结束索引-开始索引）//2。

2.在中间索引处查找该项目。如果在中间索引处找到该项，返回其位置。

3.如果要查找的项目大于中间索引处的项目，通过为其指定值：中间索引 + 1来更新开始索引。

4.否则，如果要查找的项小于中间索引处的项，则通过为其指定值：中间索引 - 1来更新结束索引。

5.重复步骤2至4，直到开始索引小于或等于结束索引。如果开始索引大于结束索引，则找不到该项。

下面的脚本在Python中实现了二分查找算法。该脚本在nums列表中查找项目15。

nums = [4,9,15,21,25,28,35,38,40,45]

item = 15

start_index = 0

end_index = len(nums) - 1

value_found = False

while start_index <= end_index:

    mid_index = start_index + (end_index - start_index) // 2

    item_mid_index = nums[mid_index]

    if item == item_mid_index:

        value_found = True

        print('项目已找到, 其索引是', mid_index)

        break;

    elif item > item_mid_index:

        start_index = mid_index + 1

    else:

        end_index = mid_index - 1

if value_found == False:

    print('项目未找到')

运行脚本后的结果如下图1所示。

图1

试运行我们的二分查找算法代码

可以通过为每个迭代输入start_index、end_index和mid_index的值来试运行上述代码。你将看到，在第三次迭代期间，在第二个索引处找到了项目15。

nums = [4,9,15,21,25,28,35,38,40,45]

start_index = 0

end_index = 9

item = 15

第1次迭代

mid_index = 0 + (9 – 0)//2 = 0 + 4 = 4

item_mid_index = nums[4] = 25

item (15) < item_mid_index (25)

end_index = mid_index – 1 = 4 – 1 = 3

第2次迭代

mid_index = 0 + (3 – 0)//2 = 0 + 1 = 1

item_mid_index = nums[1] = 9

item (15) > item_mid_index (9)

start_index = mid_index + 1 = 1 + 1 = 2

第3次迭代

mid_index = 2 + (3 – 2)//2 = 2 + 0 = 2

item_mid_index = nums[2] = 15

item (15) == item_mid_index (15)

return mid_index

使用函数实现二分查找算法

也可以将自己的二分查找算法实现为Python函数。

例如，下面的脚本实现了一个名为bin_search()的函数，该函数接受输入数组和要在数组中查找的项。如果找到该项，则该函数返回该项的索引。否则，该函数将返回None。

def bin_search(arr, item):

    start_index = 0

    end_index = len(arr) - 1

    while start_index <= end_index:

        mid_index = start_index + (end_index - start_index) // 2

        item_mid_index = arr[mid_index]

        if item == item_mid_index:

            return mid_index

        elif item > item_mid_index:

            start_index = mid_index + 1

        else:

            end_index = mid_index - 1

    return None

下面的脚本调用binary_search()函数来查找nums列表中项目40的位置。

nums = [4,9,15,21,25,28,35,38,40,45]

item = 40

index = bin_search(nums, item)

if index != None:

    print('项目已找到,其索引是', index)

else:

    print('项目未找到')

运行脚本后的结果如下图2所示。

图2

二分查找函数也可用于查找排序列表中非数字项的位置。看下面的示例：

animals = ['cat','dog','horse','jaguar','kangaroo']

item = 'jaguar'

index = bin_search(animals, item)

if index != None:

    print('项目已找到,其索引是', index)

else:

    print('项目未找到')

运行脚本后的结果如下图3所示。

图3

由于二分查找算法在每个查找步骤中将数组分为两部分，因此二分查找的最坏情况下复杂度为log（n）。

欢迎到知识星球：完美Excel社群，进行技术交流和提问，获取更多电子资料，并通过社群加入专门的微信讨论群，更方便交流。