在Python中执行二分查找
标签：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）。
腾讯云开发者
